[LeetCode]39. 组合总和(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]
]

解题思路

深度优先搜索(DFS)/回溯法。
对于需要保存结果的 DFS 来说,需要传入当前的搜索路径,以便在到达符合条件的叶子节点时保存到结果集。
思路:以 target 为根节点,依次对于 candidates 中的所有数字作减法成为每一个分支。当减到 0 的时候,说明该条路径是一个合法的路径,将该路径保存到结果集中;当减到负数的时候,说明该条路径不是一个合法的路径,终止深搜。
总体上,DFS 可以按照树形图来写代码。

图源,侵删。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
length = len(candidates)
if length < 1:
return []

candidates.sort()
res= [] # 结果集
path = [] # 路径栈
self.__dfs(0, length, candidates, target, path, res) # 从根节点开始 DFS
return res

def __dfs(self, left, right, candidates, target, path, res):
# 传入 left 和 right 表示当前可取数字的范围
# 如果不做限制,那么最终会有重复的结果

if target == 0:
# 到叶子节点时若为 0,则说明这是一条可行路径
# 需要使用 path 的 copy:path[:] 或者 path.copy()
res.append(path[:])

for idx in range(left, right):
reminder = target - candidates[idx]
if reminder < 0:
# 如果减了 idx 处的数小于 0,那么 idx 后面的数更不可能
# 退出循环会回溯到上一个添加的节点处,修改该数字到下一个可能的数字
break
path.append(candidates[idx])
# 从该节点往下遍历,只能取包含 idx 本身以及之后的数字
self.__dfs(idx, right, candidates, reminder, path, res)
path.pop() # 该节点回溯回来的时候把本来加进去的数字删掉,准备加入下一个数字

执行用时 : 108 ms
内存消耗 : 13.9 MB

参考

https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2