40 组合总和（回溯算法）

本文主要是介绍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

这篇关于40 组合总和（回溯算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！