Python|回溯算法解决力扣排列组合2
问题描述
给定一个数组 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 |
|---|
结语
回溯算法其实是一个架子，我们只需要根据题目的相应情况来调整回溯的条件与跳出的条件，相当于是套公式。只需要记住“公式”，理解算法思路，便可以用来轻松解题。