代码随想录day25

 1 class Solution {
 2 private:
 3     vector<vector<int>> result;
 4     vector<int> path;
 5     //1、确定回溯函数返回值和参数
 6     //n - 目标值， k - 集合数目， sum - 用来匹配的和， 每次回溯的索引
 7     void backtracking(int n, int k, int sum, int startIndex) {
 8         //2、确定回溯停止的条件
 9         if (path.size() == k) {
10             if (sum == n) result.push_back(path);
11             return;
12         }
13         //3、确定单层回溯的逻辑
14         for (int i = startIndex; i <= 9; i++) {
15             sum += i;
16             path.push_back(i);
17             backtracking(n, k, sum, i + 1);
18             sum -= i;
19             path.pop_back();
20         }
21     }
22 public:
23     vector<vector<int>> combinationSum3(int k, int n) {
24         result.clear();
25         path.clear();
26         backtracking(n, k, 0, 1);
27         return result;
28     }
29 };

 1 class Solution {
 2 private:
 3     //创建字符集
 4     const string letterMap[10] = {
 5         "", // 0
 6         "", // 1
 7         "abc", // 2
 8         "def", // 3
 9         "ghi", // 4
10         "jkl", // 5
11         "mno", // 6
12         "pqrs", // 7
13         "tuv", // 8
14         "wxyz", // 9
15     };
16 public:
17     //创建存放结果的变量
18     vector<string> result;
19     string s;
20     //1、确定回溯函数的参数和返回值
21     //digits - 输入的字符串， index - 记录遍历的编号
22     void backtracking(const string& digits, int index) {
23         //2、确定回溯截止的条件
24         if (index == digits.size()) {
25             result.push_back(s);
26             return;
27         }
28         int digit = digits[index] - '0';
29         string letters = letterMap[digit];
30         //3、确定回溯函数的单层逻辑
31         for (int i = 0; i < letters.size(); i++) {
32             s.push_back(letters[i]);
33             backtracking(digits, index + 1);
34             s.pop_back();
35         }
36     }
37 public:
38     vector<string> letterCombinations(string digits) {
39         s.clear();
40         result.clear();
41         if (digits.size() == 0) {
42             return result;
43         }
44         backtracking(digits, 0);
45         return result;
46     }
47 };