LeetCode-47-全排列2

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) return res;
        Arrays.sort(nums);
        boolean[] visited = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, visited, res);
        return res;
    }

    public void dfs(int[] nums,int len,int depth,List<Integer> path,boolean[] visited,List<List<Integer>> res){
        if(len==depth){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<len;i++){
            if(!visited[i]){
                // visited[i-1]是因为nums[i-1]在回退的过程中刚刚被撤销选择
                if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false) continue;
                visited[i] = true;
                path.add(nums[i]);
                dfs(nums,len,depth+1,path,visited,res);
                visited[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}