Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]
have the following unique permutations:[1,1,2]
, [1,2,1]
, and [2,1,1]
.public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> tem = new ArrayList<Integer>(); boolean[] visit = new boolean[num.length]; if (num.length == 0 || num == null){ return result; } Arrays.sort(num); dfs(result, tem, num, visit); return result; } public void dfs(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tem, int[] num, boolean[] visit){ if(tem.size() == num.length){ result.add(new ArrayList<Integer> (tem)); return; } for(int i = 0; i < num.length; i++){ if(visit[i] == true){ continue; } if(i > 0 && num[i] == num[i-1] && visit[i-1] == false ){ continue; } visit[i] = true; tem.add(num[i]); dfs(result, tem, num, visit); tem.remove(tem.size()-1); visit[i] = false; } } }
与之前不同的是增加了一个if语句, 若果num[i]和num[i-1]相等但是num[i-1]又没被使用过 说明相似的情况已经出现过 要避免再出现.
boolean[] visit = new boolean[num.length];这里不用再加小括号
没有评论:
发表评论