代码随想录算法训练营day22 | 77. 组合、216.组合总和III 、17.电话号码的字母组合

碎碎念：加油
参考：代码随想录

回溯算法理论基础

回溯和递归是相辅相成的，只要有递归，就会有回溯。回溯通常在递归函数的下面。
回溯搜索到法的效率： 它其实是纯暴力的做法，不是一个高效的算法。
回溯法能解决的问题： 组合问题（不强调元素的顺序）、切割问题、子集问题、排列问题（强调元素的顺序）、棋盘问题（N皇后）
如何理解回溯法： 所有回溯法都可以抽象为一个树行结构。一般来说树的宽度是回溯法中处理的集合的大小，树的深度就是递归的深度。
回溯法的模板：

void backtracking(参数){if (终止条件) {收集结果;return;}for (遍历集合的每一个元素){处理节点;递归函数;回溯操作; // 撤销处理节点}return;
}

77. 组合

题目链接

77. 组合

思想

看到这题我们自然而然想到暴力做法，如果k是2，那么就用两层for循环，但是k稍微大点，这么做就显然做不出来了，时间复杂度太大了。
回溯法是通过递归来控制有多少层for的。
上面提到过，回溯法做题可以抽象出一个树形图，本题抽象出来的树形图如图。

叶子节点就是我们要求的所有组合。通过维护一个参数startindex来控制搜索的起始位置。
定义一个一维数组path，定义一个二维数组result
回溯三部曲：

1. 递归函数的参数和返回值：一般返回值都是void，参数n，k，startindex
2. 终止条件：path的大小等于k，就要收割结果。
3. 单层搜索的逻辑：从startindex开始遍历后面的元素，用path收集路径上的元素，递归下一层，回溯（把之前收集到的一个元素pop出去）。

剪枝：

优化上面单层搜索的逻辑：
其实图里每个节点都是for循环。那么我们要做的优化就在于for循环里i的范围。
path存放着已经选取到的元素，还剩k-path.size()需要选取，这些元素至多要从n-(k-path.size())+1的位置开始。
[x, n]的数组长度起码应该是k-path.size()，这才有继续搜索的必要， 有 n-x+1 = k-path.size() ，得 x = n+1 - (k-path.size()), 而且这个x是可以作为起点往下搜的，也就是for(i = s; i<=x; i++) 这里的x是可以取到的。
体现在代码里，修改为i <= n-(k-path.size())+1即可。

题解

// cpp
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.push_back(path);return;}for (int i = startIndex; i <= n; i++) {path.push_back(i);backtracking(n, k, i + 1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

# python 剪枝优化
class Solution:def __init__(self):self.result = []self.path = []def backtracking(self, n, k, startIndex):if len(self.path) == k:self.result.append(self.path[:])returnfor i in range(startIndex, n - (k - len(self.path)) + 2):self.path.append(i)self.backtracking(n, k, i + 1)self.path.pop()def combine(self, n: int, k: int) -> List[List[int]]:self.backtracking(n, k, 1)return self.result

反思

注意组合是无序的，组合中的元素只能使用一次。

216.组合总和III

题目链接

216.组合总和III

思想

和上一题的区别在于多了一个关于和的限制。
注意本题不强调元素的顺序，比如126和216是同一个组合。
树形结构：

定义一个一维数组path，定义一个二维数组result
回溯三部曲：

1. 参数和返回值：返回值为void，参数targetSum，k，sum，startIndex。
2. 终止条件：path的size==k，判断sum和targetSum是否相等，相等就把path加入result，否则直接返回。
3. 单层递归逻辑：从startIndex开始遍历，取数加入path，计算sum，下一层递归（startIndex传入i+1），pop出刚加入的数，修改sum。

剪枝优化：
如果sum>targetSum，直接返回；
在for循环那里也可以做剪枝，体现在代码里，修改为i <= 9-(k-path.size())+1即可。

题解

// cpp
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(int targetSum, int k, int sum, int startIndex) {if (path.size() == k) {if (sum == targetSum) result.push_back(path);return;}for (int i = startIndex; i <= 9; i ++) {sum += i;path.push_back(i);backtracking(targetSum, k, sum, i + 1);sum -= i;path.pop_back();}}
public:vector<vector<int>> combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n, k, 0, 1);return result;}
};

# python 剪枝优化
class Solution:def __init__(self):self.path = []self.result = []def backtracking(self, targetSum, k, currentSum, startIndex):if currentSum > targetSum: # 剪枝returnif len(self.path) == k:if currentSum == targetSum:self.result.append(self.path[:])returnfor i in range(startIndex, 9 - (k - len(self.path)) + 2):currentSum += iself.path.append(i)self.backtracking(targetSum, k,currentSum, i + 1)currentSum -= iself.path.pop()def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.backtracking(n, k, 0, 1)return self.result

反思

注意组合是无序的，组合中的元素只能使用一次。

17.电话号码的字母组合

题目链接

17.电话号码的字母组合

思想

树形图如图：

回溯三部曲：

1. 参数和返回值：返回值是void，参数是digits，index（当前遍历到哪个数字了）
2. 终止条件：index==digits.size() 收获结果
3. 单层递归逻辑：用index取数字，用数字找字符串，接下来遍历得到的字符串，把字母放入s，调用递归函数（index+1），再把s取出来（回溯）。

回溯过程也可以隐藏在参数里。

题解

class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}string letters = letterMap[digits[index] - '0'];for (int i = 0; i < letters.size(); i ++) {s.push_back(letters[i]);backtracking(digits, index + 1);s.pop_back();}}vector<string> letterCombinations(string digits) {if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};

class Solution:def __init__(self):self.letterMap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]self.result = []self.s = ""def backtracking(self, digits, index):if index == len(digits):self.result.append(self.s)returnletters = self.letterMap[int(digits[index])]for i in range(len(letters)):self.s += letters[i]self.backtracking(digits, index + 1)self.s = self.s[:-1]def letterCombinations(self, digits: str) -> List[str]:if len(digits) == 0:return self.resultself.backtracking(digits, 0)return self.result

反思

前两题都是在一个集合里来求组合，所以需要用到startIndex，本题是在不同的集合里，不需要用参数来控制之前遍历的元素。