题目：39. 组合总和
链接：https://leetcode-cn.com/problems/combination-sum
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
解题：
1、DFS典型应用。
代码：
代码语言：javascript复制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
