程式碼隨想錄演演算法訓練營第二十五天| 216.組合總和III 17.電話號碼的字母組合

216.組合總和III

卡哥建議：如果把組合問題理解了，本題就容易一些了。

題目連結/文章講解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html

視訊講解：https://www.bilibili.com/video/BV1wg411873x

做題思路：

本題k相當於樹的深度，9（因為整個集合就是9個數）就是樹的寬度。

例如 k = 2，n = 4的話，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（個數） = 2, n（和） = 4的組合。

選取過程如圖：

圖中可以看出遍歷的深度，就是輸入"23"的長度，而葉子節點就是我們要收集的結果，輸出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

需要一個字串s來收集葉子節點的結果，然後用一個字串陣列result儲存起來，

程式碼中的 index 是從0開始的，是記錄遍歷第幾個數位了，就是用來遍歷digits的（題目中給出數位字串「23」），就是下標，同時index也表示樹的深度。

本題程式碼：

 1 class Solution {
 2 private:
 3     const string letterMap[10] = { //二維陣列，10行，列並沒有定義，但能看出來
 4         "", // 0
 5         "", // 1
 6         "abc", // 2
 7         "def", // 3
 8         "ghi", // 4
 9         "jkl", // 5
10         "mno", // 6
11         "pqrs", // 7
12         "tuv", // 8
13         "wxyz", // 9
14     };
15 public:
16     vector<string> result;//放葉子節點的結果
17     string s;
18     void backtracking(const string& digits, int index) {
19         if (index == digits.size()) {
20             result.push_back(s);
21             return;
22         }
23         int digit = digits[index] - '0';        // 將index指向的數位轉為int，比如digits[0]="2",減完後，就是2了
24         string letters = letterMap[digit];      // 取數位對應的字元集，比如，letterMap[2]="abc",然後在二維陣列裡就能找到對應的字串
25         for (int i = 0; i < letters.size(); i++) { //樹的結構，看上圖
26             s.push_back(letters[i]);            // 處理
27             backtracking(digits, index + 1);    // 遞迴，注意index+1，一下層要處理下一個數位了
28             s.pop_back();                       // 回溯
29         }
30     }
31     vector<string> letterCombinations(string digits) {
32         s.clear();
33         result.clear();
34         if (digits.size() == 0) {
35             return result;
36         }
37         backtracking(digits, 0);
38         return result;
39     }
40 };