39. 组合总和
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合
示例
- 示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]- 示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]解题思路
思路
由题可知，原数组元素不重复，题目需要寻找一个符合条件的组合，且原数组的单个元素可以重复使用，只要结果中的子组合互不相同即可；求解
原数组的单个元素可以重复使用
意味着下一个 for 循环中的元素选取，要从前一个元素开始，因为可以重复使用，不然如果跟着 for 的自增变量 i 走，会漏掉可能解
将自增变量 i 传递下去
终止条件
target 一一减去符合组合的元素，最终为 0 ，才是一个符合题意的组合
代码模板：
解决一个回溯问题，实际上就是一个决策树的遍历过程。我们只需要考虑三个问题：
路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。
其对应的代码模板就是：
res = []
def back_track(路径，选择列表):
if 满足结束条件:
res.add(路径)
return
for 选择 in 选择列表:
做选择
back_track(路径，选择列表)
撤销选择其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」(还原选择状态进行下一次选择)
代码
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let n = candidates.length,
res = [],
tempRes = [];
let backTrack = (tempRes, target, start) => {
if (target < 0) {
return;
}
if (target === 0) {
res.push(tempRes);
return;
}
for (let i = start; i < n; i++) {
tempRes.push(candidates[i]);
backTrack(tempRes.slice(), target - candidates[i], i);
tempRes.pop();
}
};
backTrack(tempRes, target, 0);
return res;
};
