Python培训

400-996-5531

热门课程:

Python培训 > 自学Python > 正文

Python之中力扣之组合总和

发布：Python培训
来源：自学Python
时间：2020-04-29 15:47

给定一个数组 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]

]

解决方案：

这道题的主要注意事项是一次组合中不能重复使用一个数字，与之区别开的另外一道题可参考力扣“组合总和1”题目。

这道题还是是一道较为基础的回溯算法题，根据回溯算法固有规律，我们可以将其看作是一种探索法。

先对candidates进行一个排序，创建一个result列表，储存得到的结果，用于最后输出。然后从第一个数开始尝试，回溯条件为当combination即当前相加和大于target时，就回到上一步;如果combination等于target，便存入result中并且继续回溯，直到结束。

这里值得注意的一个操作是剪枝，及不让元素被重复选取。直接上代码：

for i in range(index,lenth-1): if i>index and candidates[i] == candidates[i-1]: continue

详细的更多剪枝细节可以深入探究。

Python代码：

def combinationSum2(candidates, target): result = [] candidates.sort() lenth = len(candidates) if lenth == 0: return [] def backtrack2(sums,index,combination): if sums > target: return if sums == target: result.append(combination) if sums < target: for i in range(index,lenth-1): if i>index and candidates[i] == candidates[i-1]: continue backtrack2(sums+candidates[i],i+1,combination+[candidates[i]]) backtrack2(0,-1,[]) return result

结语

回溯算法其实是一个架子，我们只需要根据题目的相应情况来调整回溯的条件与跳出的条件，相当于是套公式。只需要记住“公式”，理解算法思路，便可以用来轻松解题。