DFS实现Combination Sum时如何输出不重复的唯一结果？

你当前代码的问题是每次递归都会从头遍历整个候选数组，导致不同排列顺序的相同组合被重复统计，比如[2,2,3]和[2,3,2]本质是同一个组合，但因为选取顺序不同被当成了两个结果。

组合和排列的核心差异是不考虑元素顺序，我们可以通过强制规定选取顺序避免重复，通用规则如下：

• 每次递归只能从当前位置及之后的候选元素中选取，禁止回头选之前的元素，从根源上消除顺序不同导致的重复
• 如果题目允许同一个元素被重复选取：下一层递归的起始遍历下标等于当前选中元素的下标
• 如果题目不允许同一个元素被重复选取：下一层递归的起始遍历下标等于当前选中元素的下标+1
• 如果候选数组本身存在重复值：先对数组排序，遍历的时候跳过和前一个值相同的元素，避免相同值的不同元素生成重复组合

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]
 */
var combinationSum = function (candidates, target) {
    let distinct = []
    // 新增start参数，标记当前递归的起始遍历下标
    let dfs = (target, list = [], start) => {
        if (target === 0) {
            distinct.push(list)
            return
        }
        // 从start开始遍历，不选之前的元素
        for (let i = start; i < candidates.length; i++) {
            const candidate = candidates[i]
            let diff = target - candidate;
            if (diff >= 0) {
                // 下一层递归起始下标还是i，允许重复选取当前元素
                dfs(diff, [...list, candidate], i)
            }
        }
    }
    // 初始调用起始下标为0
    dfs(target, [], 0)
    return distinct
};

代码修改说明 #

1. 给dfs函数新增start参数，用来限制本轮递归允许选取的元素范围
2. 遍历候选数组时从start下标开始，不再回头选取之前已经考虑过的元素，从根源上避免了顺序颠倒的重复组合
3. 下一层递归传入的起始下标为当前遍历的下标i，符合本题允许重复选取同一元素的要求。如果是不允许重复选取的组合问题，这里传入i+1即可通用。

用你给出的测试用例candidates = [2,3,6,7]，target = 7测试，输出结果为[[2,2,3],[7]]，和预期一致。

内容的提问来源于stack exchange，提问作者Austen Stone