Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] num) { // Start typing your Java solution below // DO NOT write main() function if(num.length == 0)return null; ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); int[] perm = new int[num.length]; boolean[] used = new boolean[num.length]; for(int i = 0 ; i < num.length ; i++){ used[i] = false; } recursion(num,used,result,0,perm); return result; } public void recursion(int[] num,boolean[] used,ArrayList<ArrayList<Integer>> result ,int level, int[] perm){ if(level == num.length){ ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0 ; i < perm.length; i++){ list.add(perm[i]); } result.add(list); return; } for(int i = 0; i < num.length ; i++){ if(!used[i]){ used[i] = true; perm[level] = num[i]; recursion(num,used,result,level + 1,perm); used[i] = false; } } } }
public class Solution { public List<List<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<Integer>(); dfs(result,list,num,new boolean[num.length]); return new ArrayList<List<Integer>>(result); } public void dfs( ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] num, boolean[] used){ if(list.size() == num.length){ result.add(new ArrayList<Integer>(list)); return; } else{ for(int i = 0 ; i < num.length ; i++){ if(!used[i]){ used[i] = true; list.add(num[i]); dfs(result,list,num,used); list.remove(list.size()-1); used[i] = false; } } } } }