使用 JavaScript 解答 LeetCode 第 40 题,组合总和ii,中等难度。
题目
原题链接
本题目是 LeetCode 题库第 40 题,由此访问。
题目描述
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
解题
AC 样例
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
// 边界条件处理
if(candidates.length == 0) return [[]];
// 升序排序,便于排除数据重复
candidates = candidates.sort((a, b) => a - b);
const res = [];
helper(candidates, target, res, 0, []);
return res;
};
const helper = (ca, t, res, ci, cu) => {
if(t < 0) return;
if(t == 0) {
res.push(Array.from(cu));
return ;
}
for (let i = ci; i < ca.length; i++) {
// 排除数据重复
if(i == ci || ca[i] !== ca[i-1]) {
cu.push(ca[i]);
helper(ca, t-ca[i], res, i+1, cu);
cu.pop();
}
}
}
解题思路
本题同第 39 题组合总和为配套题目,解题思路基本相同,可以参见 LeetCode:39.组合总和的题解。
本题在上述题解基础上增加了对重复数据处理的步骤,包括对数据做升序排序,以及在递归操作中对相邻两数据相同时不予处理。这两步操作使相同数据相邻,并在遍历时快速排除,以使题解符合题目要求。