216. 組合總和 III

找出所有相加之和為 n 的 k 個數的組合，且滿足下列條件：

• 只使用數字1到9
• 每個數字 最多使用一次
  返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

示例 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
沒有其他符合的組合了。

示例 3:

輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內使用4個不同的數字，我們可以得到的最小和是1+2+3+4 = 10，因為10 > 1，沒有有效的組合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

回溯算法

class Solution {
public:// 主函數，調用回溯函數并返回結果vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return result;}private:vector<vector<int>> result; // 存儲所有符合條件的組合vector<int> path; // 當前的組合// 回溯函數void backtracking(int k, int n, int sum, int start) {// 如果當前的數字和超過了n，直接返回if (sum > n)return;// 如果路徑中的數字數量達到了kif (path.size() == k) {// 并且這些數字的和恰好等于nif (sum == n)result.push_back(path); // 將其添加到結果集中return; // 返回上一層}// 循環從start開始到9// 減去 (k - path.size()) + 1 是為了保證有足夠的數字可以選擇for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {path.push_back(i); // 把當前數字加入到當前路徑sum += i; // 更新當前數字之和// 繼續回溯，尋找下一個數字，起始數字是當前數字加1backtracking(k, n, sum, i + 1); path.pop_back(); // 回溯，將當前數字從路徑移除sum -= i; // 更新當前數字之和}// 函數返回到上一層調用}
};

這段代碼是一個經典的回溯算法案例，它通過遞歸和回溯來尋找所有可能的數字組合。算法逐步構建每個可能的組合，并且在遞歸的每一層中，都會檢查當前的組合是否滿足條件。如果條件滿足，它會將組合加入到最終的結果集中；如果不滿足，它會回溯到上一層繼續嘗試其他的數字。通過這種方式，算法能夠找到所有符合題目要求的組合。