博客

求目标数组的组合问题中，很令人头疼的就是去重。

可以举

LeetCode90

这个经典例子来做说明：

该题要求输出给定数组的所有可能子集，注意解中不能包含重复子集。

该题给的测试用例为[1,2,2]。

很明显如果我们用暴力循环的方式进行求解时会出现两个[1,2]子集，尽管两个2的下标不同，但这是不被允许的。这里可能会有人想到用完一个数后就标记该数，后续遇到该数时就跳过，这种思路是正确的，但牵扯到这个标记是放在树枝遍历还是树层遍历中。附：关于树枝遍历与树层遍历，可以看Carl哥在代码随想录中的总结。

🔗

这里我们给出一个通用的解决方案，底层思路就是将这个标记数组放在树层遍历中，熟悉回溯算法的同学应当知道树层遍历发生在backtracing函数的for循环之外，因此该数组定义在for循环之外即可。

    let backtracing = (startIndex) =>{
        res.push([...path])
        if(startIndex === nums.length) return ;
        let used = []; //此处为标记数组的定义
        for(let i = startIndex;i<nums.length;i++){
            if(i >0 && candidates[i] === candidates[i-1] && used[candidates[i] + 10] ) continue;
            path.push(candidates[i]);
            used[candidates[i] + 10]  = true;
            backtracing(i+1);
            path.pop()
        }
    }

注：代码段为LeetCode90中的部分代码段，读者关注used数组的定义位置和判断规则即可。

因为该数组只定义在该层的backtracing中，回溯三部曲的第三步中不必添加used数组的状态转换，只需要定义后在for循环内添加判断即可。