39-组合总和.md

39-组合总和

原题

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

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1：

输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]

const combinationSum = function (candidates, target) {
    const DFS = (res, curRes, curSum, index) => {
        if (curSum === target) {
            res.push(curRes.slice());
        }
        
        if (curSum > target) {
            return;
        }
        
        for (let i = index; i < candidates.length; i++) {
            if (curSum < target) {
                curRes.push(candidates[i]);
                DFS(res, curRes, curSum + candidates[i], i++);
                curRes.pop();
            }
            else {
                break;
            }
        }
    }
    
    let res = [];
    DFS(res, [], 0, 0);
    return res;
}