Appearance
40. 组合总和 II
原题链接：LeetCode 40. 组合总和 II
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
**注意：**解集不能包含重复的组合。
示例 1:
[10,1,2,7,6,1,5]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
- `1 <= candidates.length <= 100`
- `1 <= candidates[i] <= 50`
- `1 <= target <= 30`
难度： Medium
题解代码
javascript
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
const ret = []
candidates = candidates.sort((m, n) => m -n)
backTrack(candidates, target, [], ret, 0)
return ret
};
function backTrack (nums, remain, path, ret, start) {
if (!remain) ret.push(path)
if (start > nums.length - 1) return
for (let i = start; i < nums.length; i++) {
if (nums[i] > remain) return // 这里减枝
path.push(nums[i])
backTrack(nums, remain - nums[i], [...path], ret, i + 1)
path.pop()
while(nums[i + 1] === nums[i]) {
i++
}
}
}