Open Ray-56 opened 3 years ago
深度递归,以[2, 3, 5]
举例
从2
开始
选择自己,就是[2]
再与[2, 3, 5]
,再次递归
不选自己,就是[]
再与[2, 3, 5]
,直到条件满足退出递归
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const ret = [];
dfs(target, [], 0);
function dfs(target, combine, index) {
if (index >= candidates.length) return;
if (target === 0) {
ret.push(combine);
return;
}
// 不选当前
dfs(target, combine, index + 1);
// 满足条件,选择当前
if (target - candidates[index] >= 0) {
dfs(target - candidates[index], [...combine, candidates[index]], index);
}
}
return ret;
};
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
示例 1:
示例 2:
提示: