原题地址：组合总和
给定一个无重复元素的数组 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]
]
回溯算法
对每个位置的数字，依次尝试不同的重复次数，判断是否能得到可用的组合。
具体的实现代码如下：
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum1 = function(candidates, target) {
candidates.sort((a, b) => a - b);
/**
* 求解从某一个位置开始，后面部分得到的和为sum的组合
* @param index 开始位置
* @param sum 要求的和
* @returns {[]|Array} 得到的结果集
*/
const combine = (index, sum) => {
// 数组已处理完，不会有新的结果出现，返回空数组
if (index === candidates.length) {
return [];
}
// 因为已经排过序，如果要处理的第一个数就比要得到的sum大，显然求和后是要大于sum的
if (candidates[index] > sum) {
return [];
}
let result = [];
for (let i = 0; i <= Math.floor(sum/candidates[index]); i ++) {
// 得到了结果，将结果保存到result中
if (sum === i * candidates[index]) {
result.push(new Array(i).fill(candidates[index]));
} else {
// 将sum减去i次第一个数，然后递归求解后面的部分
let array = combine(index + 1, sum - i * candidates[index]);
// 如果后面部分有解，就进行合并
if (array.length > 0) {
for (let j = 0; j < array.length; j ++) {
result.push(new Array(i).fill(candidates[index]).concat(array[j]));
}
}
}
}
return result;
};
// 从0开始求解
return combine(0, target);
};
测试：
let start = new Date();
const test = combinationSum1;
console.log(test([2,3,6,7], 7)); // [ [ 7 ], [ 2, 2, 3 ] ]
console.log(test([2,3,5], 8)); // [ [ 3, 5 ], [ 2, 3, 3 ], [ 2, 2, 2, 2 ] ]
console.log(new Date().getTime() - start.getTime()); // 9
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 8,2019