LeeCode题库第四十题

40.组合总和II 

项目场景：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]

提示:

1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30

---

问题描述

        这题类似于题库第三十九题，但是要求解集中不能出现重复的组合，于是排序之后需要判断此时递归到的元素是否和前一个元素相等，i与start相等的时候，当前i为第一层级即使与前一个元素相等也不需跳过，之后不断进行递归和恢复现场即可。

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(state:List[int],target:int,choices:List[int],start:int,res:List[List[int]]): if target==0: res.append(list(state)) return for i in range(start,len(candidates)): if target-candidates[i]<0: break if i>start and choices[i]==choices[i-1]: continue state.append(choices[i]) backtrack(state,target-candidates[i],choices,i+1,res) state.pop() state=[] candidates.sort() start=0 res=[] backtrack(state,target,candidates,start,res) return res

        本题提交情况。

 

        以上为本篇文章的全部内容，感谢你抽出宝贵的时间阅读这篇文章。如果你有任何疑问或建议，欢迎在评论区留言，我们一起交流进步。愿你的代码之路越走越顺，生活充满阳光！