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 <= 100
• 1 <= candidates[i] <= 50
• 1 <= 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))returnfor i in range(start,len(candidates)):if target-candidates[i]<0:breakif i>start and choices[i]==choices[i-1]:continuestate.append(choices[i])backtrack(state,target-candidates[i],choices,i+1,res)state.pop()state=[]candidates.sort()start=0res=[]backtrack(state,target,candidates,start,res)return res

        本题提交情况。

 

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