题解 | #有重复项数字的全排列#

如何思考剪枝过程？

• 数组中有重复数字会导致出现重复的排列，因为要对原数组循环遍历每个数字来递归获取排列数。
• 要阻止出现重复排列的情况，就要在同一层循环中不使用重复的数字来递归，为了方便判断是否为重复的数字，可以先对数组进行排序，再判断相邻的两个数字是否重复即可。
• used数组用于判断某个数字是否被使用过，如果被使用过则跳过这个数字避免重复使用。但在重复数字的场景下，如果数字没被使用过还需要判断他是否是跟前一个数字重复，如果重复了也要跳过这个数字。
• used数组只在递归过程会逐个变true，如果used[i-1]为false说明和当前数字相同的上一个数字在上一次循环中被递归使用了，回溯后当前层为false，所以如果当前数字和前一个数字相同，就不能再选择这个数字进入递归。
• 因为要判断两个相邻的数字，所以起码要从第二个数字开始判断，即i>0。

参考

https://blog.nowcoder.net/n/50274e5a9c4142be9fa551fba14b6f6a?f=comment

/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
function permuteUnique( num ) {
    const ret = []
    const used = Array.from(num, (item) => item = false);  // 用于判断数组中的元素是否使用过，如果使用过则跳过当前元素
    num.sort();  // 为了能方便的判断两个相邻数字是否相同，需要先对数组进行排序
    // write code here
    function dfs(num, ansArray=[]) {
        if (ansArray.length === num.length) {
            ret.push(ansArray.slice());  // 要传入一个副本，也可以用[...ansArray]
            return;
        }
        for (let i = 0; i < num.length; ++i) {
            // 有重复数字后会导致出现重复的排列，要阻止这种情况则必须要同一层中重复数字不能重复递归使用，关键是如何判断同一层重复数字的逻辑。
            // used数组只在递归过程会逐个变true，如果当前为true上一个为false说明这是同一层循环中的上一次循环回溯后变false了，此时两者在同一层。
			// 因为要判断两个相邻的数字，所以起码要从第二个数字开始判断，即i>0
            if (used[i] || (i > 0 && num[i-1] === num[i] && !used[i-1])) {  
                continue;
            }
            
            ansArray.push(num[i]);
            used[i] = true;
            dfs(num, ansArray);  // 递归传入的是原数组，通过判断原数组的元素是否使用过来缩减元素范围，而不是通过传入削减后的数组切片，这样会丢失元素
            used[i] = false;
            ansArray.pop();
        }
    } 

    dfs(num, []);

    return ret;
}
module.exports = {
    permuteUnique : permuteUnique
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        boolean[] used = new boolean[num.length];
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Arrays.sort(num);
        dfs(num, arr, used);

        return this.res;
    }

    private void dfs(int[] num, ArrayList<Integer> arr, boolean[] used) {
        if (num.length == arr.size()) {
            this.res.add(new ArrayList<Integer>(arr));
            return;
        }

        for (int i = 0; i < num.length; ++i) {
            if (used[i] || (i > 0 && num[i] == num[i-1] && used[i-1] == false)) {
                continue;
            }

            arr.add(num[i]);
            used[i] = true;
            dfs(num, arr, used);
            used[i] = false;
            arr.remove(arr.size()-1);
        }

    }
}