2015年4月2日星期四

Permutations II leetcode

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];这里不用再加小括号

没有评论:

发表评论