leetcode刷题-回溯算法01

理论基础

代码随想录文档讲解

基本介绍

回溯是递归的副产品，只要有递归就会有回溯。
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。【纯暴力搜索】

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

回溯法解决的问题都可以抽象为树形结构。

77. 组合

leetcode题目链接
代码随想录文档讲解

思路：

两层for循环（大小为2）
三层for循环（大小为3）

依照树形结构->回溯算法
三部曲：
递归函数返回值
确定终止条件
确定单层递归（搜索）逻辑

伪代码（C++）：

// 二维数组 result
// 一维数组 path（路径）
void backtraccking(n,k,startIndex){ //startindex下一循环的初始位置if(path.size==k){result.push(path);return}for(i=startIndex, i<=n; i++){ // 单层搜索path.push(i);backtracking(n,k,i+1);path.pop(); // 回溯}
}

python代码：

class Solution:def backtracking(self, n, k, startindex):if(len(self.path) == k):self.result.append(self.path[:])return // 这里第一次写也忘记了for i in range(startindex, n+1):self.path.append(i)self.backtracking(n, k, i+1)self.path.pop()def combine(self, n: int, k: int) -> List[List[int]]:self.path = []self.result = []self.backtracking(n, k, 1)return self.result

扩展-剪枝

for i in range(startindex, n-(k-len(self.path))+2):

216.组合总和III

leetcode题目链接
代码随想录文档讲解

思路：

剪枝：1️⃣根据targetsum与sum
2️⃣根据k，k个之和，取9-k之后的没有意义

伪代码（C++）：

// path一维数组
// result二维数组
void backtracking(int targetSum, int k, int sum, int startIndex){if(path.size==k){ //终止条件if(targetSum == sum){result.push_back(path);}return;}for(int i=startindex; i<=9; i++){sum += 1;path.ush_back(i);backtracking(targetSum, k, sum, i+1);sum -= i;path.pop_back(i);}
}

剪枝代码

// path一维数组
// result二维数组
void backtracking(int targetSum, int k, int sum, int startIndex){if (sum > targetSum) { // 剪枝操作return; }if(path.size==k){ //终止条件if(targetSum == sum){result.push_back(path);}return;}for(int i=startindex; i<=9-(k - path.size()) + 1; i++){sum += 1;path.ush_back(i);backtracking(targetSum, k, sum, i+1);sum -= i;path.pop_back(i);}
}

python代码：

class Solution:def backtracking(self, k, startIndex, sum, targetSum):if sum > targetSum:returnif len(self.path) == k:if sum == targetSum:self.result.append(self.path[:])returnfor i in range(startIndex, 9 - (k-len(self.path)) + 2):sum = sum + iself.path.append(i)self.backtracking(k, i+1, sum, targetSum)sum = sum - iself.path.pop()def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.path = []self.result = []self.backtracking(k, 1, 0, n) // sum初始化为0return self.result

17.电话号码的字母组合

leetcode题目链接
代码随想录文档讲解

一遍过

class Solution:def backtracking(self, num, index):if index > len(num):returnif len(self.path) == len(num):self.result.append(self.path[:])returni = num[index]for a in self.dct[i]:self.path += aself.backtracking(num, index+1)self.path = self.path[:-1]def letterCombinations(self, digits: str) -> List[str]:if not digits:return []self.dct = {'2':['a', 'b', 'c'],'3':['d', 'e', 'f'],'4':['g', 'h', 'i'],'5':['j', 'k', 'l'],'6':['m', 'n', 'o'],'7':['p', 'q', 'r', 's'],'8':['t', 'u', 'v'],'9':['w', 'x', 'y', 'z']}self.path = ""self.result = []self.backtracking(digits, 0)return self.result