*77. 组合

leetcode题目地址

回溯法。result记录最终结果，cur_result记录单个组合的结果。
比较难理解的地方在于回溯要撤销对于结点的处理，也就是cur_result.pop_back();

在for循环中，cur_result.emplace_back(i);将当前元素压入单个组合结果中，递归调用来对后续元素进行组合。当递归调用结束后，需要将当前节点弹出来继续迭代下一种可能。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
class Solution {
public:void backtracking(vector<vector<int>>& result, vector<int>& cur_result, int left, int right, int k){if(cur_result.size() == k){result.emplace_back(cur_result);return;}for(int i=left; i<=right; i++){cur_result.emplace_back(i);backtracking(result, cur_result, i+1, right, k);cur_result.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> result;vector<int> cur_result;backtracking(result, cur_result, 1, n, k);return result;}
};

216. 组合总和 III

leetcode题目地址

和上题思路一致。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
class Solution {
public:int now = 0;void backtracking(vector<vector<int>>& result, vector<int>& cur_result, int left, int n, int k){if(now>n) return;if(now==n && cur_result.size() == k) {result.emplace_back(cur_result);return;}for(int i=left; i<10; i++){cur_result.emplace_back(i);now+=i;backtracking(result, cur_result, i+1, n, k);cur_result.pop_back();now-=i;}}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> result;vector<int> cur_result;backtracking(result, cur_result, 1, n, k);return result;}
};

*17. 电话号码的字母组合

leetcode题目地址

本题相对复杂，回溯过程中需要使用的字符串比较难处理。

先将每个数字对应的字符串存入一个map或数组中。

递归结束条件为访问的数字下标已经到达最后，即所有数字都访问过了。

取数字串中的对应一位数字，再去除该数字对应的字符串，对字符串进行回溯递归。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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