LeetCode 47. 全排列 II

题目链接

47. 全排列 II

题目分析

很明显的回溯问题了，与1的不同在于这个2存在重复的数字。那么我们需要考虑可靠的去重方案。
我们可以先对数组进行预排序，那么我们在回溯过程中，如果选择当前的数字之后，当前轮次的下一个选择的数字就应该是与当前数字不同的那一个，这样可以确保我们不会选出重复的方案。

代码实现

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

    public void dfs(List<List<Integer>> res, List<Integer> temp, int[] nums, boolean[] visited){
        if(temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        int idx = 0;
        while(idx < nums.length){
            if(visited[idx] == false){
                visited[idx] = true;
                temp.add(nums[idx]);
                dfs(res, temp, nums, visited);
                temp.remove(temp.size() - 1);
                visited[idx] = false;    
                int cur = nums[idx];
                while(idx < nums.length && nums[idx] == cur){
                    idx++;
                }
            }else{
                idx++;
            }
        }
    }
}