回溯算法模板
def backfunction(参数):
if (终止条件):
存放结果
return
for 元素 in 集合
处理节点
backfuction(参数)//递归
回溯,撤销处理结果
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
list_all = []
candidates.sort()
#参数
def fds(candidates,resid,ans):
#终止条件+存放结果
if resid == 0: list_all.append(ans)
if resid < 0:return
n = len(candidates)
i = 0
#对于所有的元素进行递归
while i < n:
fds(candidates[i+1:n],resid-candidates[i],ans+[candidates[i]])
#剪枝操作
j = i+1
while j < n and candidates[i] == candidates[j]: j += 1
i =j
fds(candidates,target,[])
return list_all