40 组合总和(回溯算法)

回溯算法模板

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
上一篇:数据分析面试题之Pandas中的groupby


下一篇:数字化转型——医院数字化管理平台HDMP建设历程