77. 組合

題目鏈接
文章講解

class Solution {
public:vector<vector<int>> res;  // 存儲所有的組合vector<int> path;         // 當前正在構建的組合// 回溯算法void solve(int n, int k, int start) {// 當 path 的大小達到 k，表示當前組合有效，加入結果集if (path.size() == k) {res.push_back(path);  // 將當前組合添加到結果中return;}// 從 start 開始，嘗試所有可能的數字for (int i = start; i <= n; i++) {path.push_back(i);  // 選擇當前數字solve(n, k, i + 1); // 繼續選擇下一個數字，注意這里遞歸是 i + 1，確保數字遞增path.pop_back();     // 回溯，撤銷選擇，嘗試其他可能的組合}}// 主函數，調用 solve 函數開始回溯vector<vector<int>> combine(int n, int k) {solve(n, k, 1);  // 從 1 開始遞歸return res;      // 返回所有組合結果}
};

216.組合總和III

題目鏈接
文章講解

class Solution {
public:vector<vector<int>> ans;  // 存儲所有符合條件的組合vector<int> path;         // 當前正在構建的組合int sum = 0;              // 當前組合的和// 回溯函數，遞歸地選擇數字void solve(int k, int n, int start, int &sum) {// 1. 如果選擇的數字個數達到了 k，檢查和是否為 nif (path.size() == k) {if (sum == n)  // 如果和恰好為 n，則加入結果ans.push_back(path);return;}// 2. 從 start 開始，嘗試選擇數字 1 到 9for (int i = start; i <= 9; i++) {path.push_back(i);  // 選擇當前數字sum += i;            // 更新和solve(k, n, i + 1, sum);  // 遞歸選擇下一個數字sum -= i;            // 回溯，撤銷選擇path.pop_back();     // 移除當前數字，繼續嘗試其他數字}}// 主函數，調用回溯函數開始求解vector<vector<int>> combinationSum3(int k, int n) {solve(k, n, 1, sum);  // 從 1 開始遞歸，尋找所有組合return ans;            // 返回所有組合結果}
};

17. 電話號碼的字母組合

題目鏈接
文章講解

class Solution {
public:vector<string> ans;  // 存儲所有字母組合string path;         // 當前遞歸路徑，用于存儲字母組合// 回溯函數，遞歸地生成字母組合void solve(vector<string>& s, int k, int start, const string& digits) {// 當 path 的長度達到 k（即字母組合的長度），將 path 加入到結果中if (path.size() == k) {ans.push_back(path);  // 添加當前組合到結果return;}// 獲取當前數字對應的字母組string p = s[digits[start] - '0'];// 遍歷該字母組中的每個字母，遞歸生成組合for (int i = 0; i < p.size(); i++) {path += p[i];               // 選擇當前字母solve(s, k, start + 1, digits);  // 遞歸選擇下一個數字path.pop_back();             // 回溯，撤銷選擇}}// 主函數，返回所有可能的字母組合vector<string> letterCombinations(string digits) {// 如果輸入為空，直接返回空結果if (digits.empty()) return ans;// 初始化字母映射：數字 2-9 對應的字母集vector<string> s = {"", "",                    // 0 和 1 沒有對應的字母"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};int k = digits.size();  // 目標組合的長度// 調用回溯函數，開始遞歸生成字母組合solve(s, k, 0, digits);return ans;  // 返回所有字母組合}
};