图解思路

代码

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        Deque<Integer> path = new ArrayDeque<>();

        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, 0, res, path);
        return res;
    }

    public void dfs(int[] c, boolean[] used, int level, List<List<Integer>> res, Deque<Integer> path){
        if(level == c.length){
            res.add(new ArrayList(path));
            return;
        }

        for(int i = 0; i < c.length; i++){
            //横向剪枝, 如何保证本层已经使用过的元素被剪枝呢？ !used[i-1]很关键
            //!used[i-1]含义是:以第i-1位为根节点的子树刚生成结束,从而保证c[i],c[i-1]在同一层
            if(i > 0 && c[i] == c[i-1] && !used[i-1]) continue;
            //纵向剪枝
            if(used[i]) continue;
            path.addLast(c[i]);
            used[i] = true;
            dfs(c, used, level+1, res, path);
            used[i] = false;
            path.removeLast();
        }
    }

}

dfs二刷20200711

class Solution {
    List<List<Integer>> res = new ArrayList();
    Stack<Integer> path = new Stack();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        //排个序, 确保枚举时的顺序
        Arrays.sort(nums);
        dfs(nums);
        return res;
    }

    public void dfs(int[] c){
        if(path.size() == c.length){
            res.add(new ArrayList(path));
            return;
        }

        //枚举每一个位置u, 要保证顺序
        for(int i = 0; i < c.length; i++){
            //used[i-1]记录的是 第i-1个数 在深层刚刚被使用过
            if(i > 0 && c[i] == c[i-1] && used[i-1]) continue;
            if(!used[i]){
                path.push(c[i]);
                used[i] = true;
                dfs(c);
                used[i] = false;
                path.pop();
            }
        }
    }
}