给定一个无重复元素的正整数数组 candidates 和一个正整数 target ,找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同,则两种组合是唯一的。
对于给定的输入,保证和为 target 的唯一组合数少于 150 个。
示例 1:
- 输入: candidates = [2,3,6,7], target = 7
- 输出: [[7],[2,2,3]]
中等
数组
回溯
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
candidates = candidates.sort((x, y) => x - y);
const min = candidates[0];
candidates = candidates.filter((i) => i === target || i + min <= target);
const res = [];
function backTrack(arr, index) {
if (sum(arr) > target) {
return true;
}
if (sum(arr) === target) {
res.push([...arr]);
return true;
}
for (let i = index; i < candidates.length; i++) {
arr.push(candidates[i]);
if (backTrack(arr, i)) {
arr.pop();
return;
}
arr.pop();
}
}
backTrack([], 0);
return res;
};
const sum = function (arr) {
return arr.reduce((total, i) => total + i, 0);
};
- 问题分析
- 题目和组合总和 II很相似,只是数组中的单个值可以多次使用。需要在回溯中去除对重复值的判断
i !== numIndex && candidates[i] === candidates[i - 1]
,递归时把当前值再传入backTrack(arr, i)
而不是backTrack(arr, i + 1)
- 题目和组合总和 II很相似,只是数组中的单个值可以多次使用。需要在回溯中去除对重复值的判断