图解力扣回溯及剪枝问题的模板应用

选哪个的问题

17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解题代码

class Solution {string MAPPING[10]= {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:vector<string> letterCombinations(string digits) {int n = digits.size();if(n == 0){return {};}vector<string> ans;string path(n, 0);auto dfs = [&](this auto&& dfs, int i){if(i == n){ans.push_back(path);return;}for(char c: MAPPING[digits[i] - '0']){path[i] = c;//元素覆盖dfs(i+1);}};dfs(0);return ans;}
};

图解

path存储每次得到的序列
核心代码：

for(char c: MAPPING[digits[i] - '0']){path[i] = c;dfs(i+1);
}

复杂度

时间复杂度：O(N*4^N)

注意，每次ans.push_back(path);也需要N的时间，所以前面乘N

空间复杂度：O(N*4^N)

ans 存储所有字母组合，共有 O(4^n) 个组合，递归存了n个点

选不选的问题

78. 子集

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题代码

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();if(n == 0){return {};}vector<int> path;vector<vector<int>> ans;auto dfs = [&](this auto&& dfs, int i){if(i == n){ans.push_back(path);return;}dfs(i+1);//不选path.push_back(nums[i]);//选dfs(i+1);path.pop_back();//恢复现场};dfs(0);return ans;}
};

图解

选不选和排列问题有个区别是，如果某个数不被选择，空元素不能直接覆盖掉上一次递归中放在这个位置的元素，所以如果元素被选择，必须在递归结束后将该位置恢复到什么都没有的状态，也就是恢复现场，保证下一次递归不被影响。

复杂度

时间复杂度：O(N2^N)
空间复杂度：O(N2^N)

两相转化

77. 组合

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

解题代码

法一：按选哪个的思路

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<int> path;vector<vector<int>> ans;auto dfs = [&](this auto&& dfs, int i){int d = k - path.size();if(d == 0){ //取path长度合适的数组加入ansans.push_back(path);return;}for(int j=i; j>=d; j--){path.push_back(j);dfs(j-1);path.pop_back();}};dfs(n);return ans;}
};

法二：按选不选的思路

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<int> path;vector<vector<int>> ans;auto dfs = [&](this auto&& dfs, int i){int d = k - path.size();if(d == 0){ //取path长度合适的数组加入ansans.push_back(path);return;}if(i < d){return;}dfs(i-1);path.push_back(i);dfs(i-1);path.pop_back();};dfs(n);return ans;}
};

图解

选哪个：

这是剪枝后的情况，下面画一个正序、不引入d的没有剪枝的情况：

显然会冗余很多，代码也贴在这供大家参考：

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<int> path;vector<vector<int>> ans;auto dfs = [&](this auto&& dfs, int i){if(path.size() == k){ //取path长度合适的数组加入ansans.push_back(path);return;}for(int j=i; j<=n; j++){path.push_back(j);dfs(j+1);path.pop_back();}};dfs(1);return ans;}
};

选不选

这种方法注意一点：只要不选，d就不会变，也就意味着两个节点如果是兄弟节点（父节点一样），那么他们的d相等，而一旦i < d，意味着这条线不可能出答案了，因为数字不够用，这个不只是剪枝，而且是必要的，不写会越界

复杂度

两个都是
时间复杂度：O(C(N,K)) （是排列组合的那个符号）
空间复杂度：O(N)

---

……可算画完了，好悬没给我累死