全排列II

来源Leetcode第47题全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

错误的回溯

这题最开始做的时候是11天前，估计是对应着全排列那道题吧，按着那道题的代码改了，有重复的输出正确，没重复的反而输出错误了，emm磨蹭了很久，今天也没找到问题所在，摸了。

错误的代码如下：

List<List<Integer>> ans = new ArrayList<>();
private boolean[] used;

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    used = new boolean[nums.length];
    nextPer(nums,0);
    return ans;
}
private void nextPer(int[] arr,int start){
    //当start==arr.length-1时，说明子序列的长度为1，就不用再往下分子序列了
    if(start==arr.length-1){
        List<Integer> temp_ans = new ArrayList<>();
        for(int i = 0 ; i < arr.length ; i++){
            temp_ans.add(arr[i]);
        }
        //System.out.println(temp_ans);
        ans.add(temp_ans);
        return ;
    }

    for(int i=start;i<arr.length;i++){
        if(!used[i]) {

            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;

            //start代表的是每一个子序列的第一个位置，我们每一层递归的任务都只有一个：
            //枚举该层子序列第一个位置可以取的值
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;

            //该层递归的子序列第一个位置已经确定了，所以又可以往下再分
            nextPer(arr, start + 1);

            //把第该层子序列第一个位置的值换成另外一个值，所以要交换回来
            temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;

            used[i] = false;
        }
    }
}

回溯 + 剪枝

来源题解

我们归纳出“剪枝”要满足的条件:

• 1、在“同一层”,它不是“从左向右数”的第1个分支(标在下图①处);
• 2、当前已经选出的数与“同一层”前一个分支已经选出的数相等(标在下图②处);
• 3、“同一层”前一个分支已经选出的数在“当前分支”还未被使用(标在下图③处)

代码如下：

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private boolean[] used;

    private void findPermuteUnique(int[] nums, int depth, Stack<Integer> stack) {
        if (depth == nums.length) {
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 修改 2：因为排序以后重复的数一定不会出现在开始，故 i > 0
                // 和之前的数相等，并且之前的数还未使用过，只有出现这种情况，才会出现相同分支
                // 这种情况跳过即可
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                stack.add(nums[i]);
                findPermuteUnique(nums, depth + 1, stack);
                stack.pop();
                used[i] = false;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        Arrays.sort(nums);

        used = new boolean[len];
        findPermuteUnique(nums, 0, new Stack<>());
        return res;
    }
}