力扣整理版八：回溯算法（待更新）

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。

组合/切割/子集/排列/棋盘

1、回溯函数返回值和参数：一般为void

2、终止条件：一般到叶子节点终止

3、回溯的遍历过程：集合的大小树的宽度，递归的深度构成树的深度。

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

------------------------------------

(1) 77 组合

(2) 216 组合总和3

------------------------------------

一、组合

1、77 组合

77. 组合 - 力扣（LeetCode）

题目描述：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

------------  python  -------------

未剪枝优化

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n + 1):  # 需要优化的地方
            path.append(i)  # 处理节点
            self.backtracking(n, k, i + 1, path, result)
            path.pop()  # 回溯，撤销处理的节点

剪枝优化

class Solution:
    def backtracing(self,n,k,index,path,result):
        if len(path)==k:
            result.append(path[:]) # 这里要[:]拷贝当前路径（切片操作），不然后面的操作会更改path path最后输出的都会是[]
            # result.append(path)是对path的引用，path.pop()会改变结果
            return
        for i in range(index,n-(k-len(path))+2):
            path.append(i)
            self.backtracing(n,k,i+1,path,result)
            path.pop()

    def combine(self, n: int, k: int) -> List[List[int]]:
        result=[]
        self.backtracing(n,k,1,[],result)
        return result

2、216 组合总和3

216. 组合总和 III - 力扣（LeetCode）

题目描述：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

------------  python  -------------

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []  # 存放结果集
        self.backtracking(n, k, 0, 1, [], result)
        return result

    def backtracking(self, targetSum, k, currentSum, startIndex, path, result):
        if currentSum > targetSum:  # 剪枝操作
            return  # 如果path的长度等于k但currentSum不等于targetSum，则直接返回
        if len(path) == k:
            if currentSum == targetSum:
                result.append(path[:])
            return
        for i in range(startIndex, 9 - (k - len(path)) + 2):  # 剪枝
            currentSum += i  # 处理
            path.append(i)  # 处理
            self.backtracking(targetSum, k, currentSum, i + 1, path, result)  # 注意i+1调整startIndex
            currentSum -= i  # 回溯
            path.pop()  # 回溯

原文地址：https://blog.csdn.net/qq_51398395/article/details/143845449

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！