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>> permuteUnique(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>>(); boolean[] used = new boolean[num.length]; for(int i = 0 ; i < num.length ; i++){ used[i] = false; } int[] perm = new int[num.length]; Arrays.sort(num); permutation(result,used,perm,0,num); return result; } public void permutation(ArrayList<ArrayList<Integer>> result, boolean[] used, int[] perm, int level, int num[]){ if(level == num.length){ ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0 ; i < num.length ; i ++){ list.add(perm[i]); } result.add(list); return; } for(int i = 0 ; i < num.length ; i++){ if(!used[i]){ perm[level] = num[i]; used[i] = true; permutation(result,used,perm,level+1,num); used[i] = false; while(i < num.length-1 && num[i] == num[i+1]){ i++; } } } } }
mistakes: 1) when i< num.length do num[i-1] == num[i] will run time error .do i < num.length-1