LeetCode刷题DAY 37：组合总合
1
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使和为 target 的组合。candidates 中的数字可以无限制重复被选取。
2
回溯算法
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试，是一种类似枚举的搜索方式。比如现在要从A走到B，当从A->B->D时发现没有办法走到B，则要退回C，从C->E，再从E->B。
3
题解
本题结合回溯算法的思想，我们首先遍历一个点a，然后计算能否从剩余的点中找到和为target-a的点。结合上述例子看一下计算过程：
- step 1：首先遍历第一个点2，arget变为5。因为5不等于0，所以需要继续向下，直至target变为-1。
- step 2：因为此时target<0，因此我们回到上一层的2并减去下一个值，即3，此时target=0，满足条件，该路径是目标路径之一。
- step 3：因为此处减3target已经变为0，则无需继续遍历比3大的值。此时回到上一层，继续减后面的值。
- step 4：同理，重复上述过程，直至所以情况全部遍历一遍，最终形成的树状图如下。
- step 5：注意上面树状图标识出的两条路径，结果是一样的，因此我们在加入路径中的点时，不要重复加入前面的点（如上一步减掉3，下一步就不要减掉3前面的2，而是从3后面的6开始减）。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
#建立递归函数，进行回溯遍历
def back(target,index,tmp):
#两个结束遍历条件
if target == 0:
path.append(tmp[::])
return
if target < 0:
return
#从当前的index后面加入点，避免重复
for i in range(index,len(candidates)):
tmp.append(candidates[i])
target -= candidates[i]
back(target,i,tmp)
#把当前层前一个点剔除，好在下一次循环中加入下一个点
tmp.pop()
target += candidates[i]
tmp = []
path = []
back(target,0,tmp)
return path本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-09-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读