day25|leetcode|C++|216. 组合总和 III|17. 电话号码的字母组合

知者行之始，行者知之成 --传习录

Leetcode 216. 组合总和 III

链接：216. 组合总和 III

thought：

以示例2为例：

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
1
2
3
4
5
6
7

下图的2-9中-是范围号

可以看出为直观的树结构，注意每轮要进行的回溯操作

完整C++代码如下：

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1,0);
        return res;
    }
private:
    vector<int>path;
    vector<vector<int>> res;
    
    void backtracking(int k,int n,int start,int curSum){
        if(curSum>n)return ;//剪枝
        if(path.size()==k){
            if(curSum==n){
                res.push_back(path);
            }
            return;
        }
        for(int i=start;i<=9;i++){
            path.push_back(i);//当前轮操作
            curSum += i;//当前轮操作
            backtracking(k,n,i+1,curSum);//递归
            path.pop_back();//回溯
            curSum -= i;//回溯
        }
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

链接：17. 电话号码的字母组合

thought：

同样的思路

完整C++代码如下：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.length()==0)return res;
        backtracking(digits,0);
        return res;
    }
private:
    vector<string>res;
    string path;
    vector<string>numberTostr{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void backtracking(string digits,int index){
        if(path.length()==digits.length()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<numberTostr[digits[index]-'2'].length();i++){
            path+=numberTostr[digits[index]-'2'][i];
            backtracking(digits,index+1);
            path=path.substr(0, path.length() - 1);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23