题目: 全排列 II

分析

该题也是全排列的题目，但是题目需要去重，所以在回溯中需要记录已经完成的全排列，从而实现去重操作。

实现去重操作可以将路径上的结点都保存下来。

回溯时候判断该结点是否可以加入路径可以用之前保存的结点进行比对，只能加入还未使用过的结点。

class Solution {
    public List<List<Integer>> solute(int[] nums) {
        int len=nums.length;
        List<List<Integer>> result=new ArrayList<>();
        if(len==0) return result;
        Arrays.sort(nums);
        boolean[] used=new boolean[len];
        ArrayList<Integer> temp=new ArrayList<>();
        dfs(result,temp,nums,used,0,len);
        return result;
    }
    
    public void dfs(List<List<Integer>> result,ArrayList<Integer> temp,int[] nums,boolean[] used,int depth,int len){
        if(depth==len){
            result.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i=0;i<len;i++){
            if(used[i]) continue;
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                continue;
            }
            temp.add(nums[i]);
            used[i]=true;
            dfs(result,temp,nums,used,depth+1,len);
            used[i]=false;
            temp.remove(temp.size()-1);
        }
    }
  
}