一天一大 lee(组合总和 II)难度:中等-Day20200910
一天一大 lee(组合总和 II)难度:中等-Day20200910
前端小书童
发布于 2020-09-24 14:30:26
发布于 2020-09-24 14:30:26
题目:
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例:
- 示例 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]
]
抛砖引玉
抛砖引玉
思路
本题逻辑的重点在不允许 candidates 的元素重复使用，但是 candidates 元素本身可能存在重复元素
- candidates 中同一个元素不能在一种组合中重复使用
- 结果元素相同组成的子元素位置不同算作一种结果
在前两天的题目中分别用：
- 指针驱动选择生成组合
- 指针约束区域枚举指定区域元素来枚举组合
两种形式处理了递归回溯子元素组合的问题
结合本题的要求：
- 指针可以协助完成同一个元素不能在一种组合中重复使用
- 如果采用指针驱动的形式，发现很难避免不同位置的元素形成相同元素的结果，而采用约束区域来枚举元素的形状，相同的元素（对 candidates 排序，相邻元素相同）被指针约束则很好避免在不同个组合中信息相同个元素
实现
- 对 candidates 排序(将相同元素排列在一起，方便指针控制元素不重复参与组合)
- 递归，从i之后遍历为参与组合元素:
- 在i指针之后遇到相同元素，则不再选择i处元素，因为此时已回溯，再次选择i处元素则形成了重复的组合
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
let _result = []
candidates = candidates.sort((a, b) => a - b)
function dfs(i, item, sum) {
if (sum === target) {
_result.push(item)
return
}
for (let x = i; x < candidates.length; x++) {
if (target - sum - candidates[x] >= 0) {
// i指针所在元素如果后面还有与其相同的元素，则不再选择i处元素，因为此时已回溯，再次选择i处元素则形成了重复的组合
if (x != i && candidates[x] == candidates[x - 1]) continue
item.push(candidates[x])
dfs(x + 1, [...item], sum + candidates[x])
item.pop()
}
}
}
dfs(0, [], 0)
return _result
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-09-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录