leetcode 39. 组合总和

https://leetcode-cn.com/problems/combination-sum/

题目

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

解：回溯搜索

思路

参考
将搜索的过程用树表达
以输入：candidates = [2, 3, 6], target = 8 为例：

以target为根节点，candidates里的数为叶子

• ▲：如果当前叶子到根节点求和>target，停止
• o：如果当前叶子到根节点求和=target，加入解集
• x：如果产生重复 剪枝

用递归实现以上逻辑

代码

var combinationSum = (candidates, target){
    const group = [];
    const dfs = (start, temp, sum) => { 
        // start是当前选择的起点索引 
        // temp是当前的集合 
        // sum是当前求和
        if (sum >= target) {
            //如果大于，直接结束递归
            if (sum == target) {
                //如果相等，将temp的拷贝加入解集
                group.push(temp.slice());
            }
            return;   // 结束当前递归
        }
        for (let i = start; i < candidates.length; i++) { 
            // 枚举当前可选的数，从start开始
            temp.push(candidates[i]);
            // 选这个数
            dfs(i, temp, sum + candidates[i]); 
            // 基于此继续选择，传i，下一次就不会选到i左边的数，达到剪枝的作用
            temp.pop();   
            // 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
        }
    };
    dfs(0, [], 0); 
    // 最开始可选的数是从第0项开始的，传入一个空集合，sum也为0
    return res;
};