回溯法模板和相关题目

回溯法的关键在于要画出一颗遍历树,根据树来确定遍历方法:
模板(有的题目需要添加visited数组记录遍历状态):

        def dfs(target, begin, path):
            # 结束条件
            if target == 0: 
                if path not in res:
                   # python的话一定要加: 才是复制,否则后续操作会修改
                    res.append(path[:]) 
                return
            for i in range(begin, len(candidates)):
                rediduel = target - candidates[i]
               # 减枝条件
                if rediduel < 0:
                    break
                path.append(candidates[i])
                dfs(rediduel, i+1, path)
                #最后要加pop
                path.pop()

相关题目: leetcode: 39, 40, 46, 47, 78, 90

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容