组合总和 II
题目：40. 组合总和 II
链接：https://leetcode-cn.com/problems/combination-sum-ii
给定一个数组 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] ]
解题：
1、DFS典型应用，和7月2日的题目非常类似。
不同的是，进行dfs时开始遍历的下标不一样。
代码：
class Solution(object):
def __init__(self):
self.res = []
self.ls = []
def dfs(self, start, target, current):
if target == 0:
self.res.append(current)
return
for i in range(start, len(self.ls)):
c = self.ls[i]
if c > target:
break
current2 = copy.copy(current)
current2.append(c)
self.dfs(i, target - c, current2)
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.ls = candidates
for i, c in enumerate(candidates):
if c > target:
break
self.dfs(i, target - c, [c])
return self.res本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-07-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读