一、题目

二、示例

//示例一
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

//示例二
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

//示例三
输入: candidates = [2], target = 1
输出: []

三、解题思路
本题主要采用的思想是递归算法，由于其中的数字可以重复使用。

如上图所示，我们通过遍历实现， 如果每一次遍历都从头开始遍历，则可能会有重复的，所以每一次递归我们保存当前index,此时只能从当前的index进行遍历。递归终止条件是：当sum的值大于或者等于target。
四、代码解析

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    let result = []
    const rec = (curArr, index, sum) => {
        if (sum >= target) {
            if (sum === target) {
                result.push([...curArr])
            }
            return
        }
        for (let i = index; i < candidates.length; i++) {
            curArr.push(candidates[i])
            rec(curArr, i, sum + candidates[i])
            curArr.pop()
        }
    }
    rec([], 0, 0)
    return result
};

五、总结