Leetcode 連結

分析

假設 ( k = 3 ) 且 ( n = 9 )，我們需要從 ( 1 ) 到 ( 9 ) 中找出所有三個相異數字、總和為 ( 9 ) 的組合。

例如，符合條件的組合有：

  • ([1, 2, 6]) → 總和 = 9 ✅
  • ([1, 3, 5]) → 總和 = 9 ✅
  • ([2, 3, 4]) → 總和 = 9 ✅

這題和 子集合問題 (subsets) 類似，都是一次挑選一個數字來探索不同的組合。主要差別在於，我們必須確保選出的數字總和等於特定目標值。

怎麼解？

使用 回溯法（backtracking）！

虛擬碼：

let combinations = List<List<Integer>>;

backtracking(int num, List<Integer> current, int k, int n, int sum) {
    if sum > n return;
    if current.size > k return;
    if sum == n and current.size == k {
        combinations.add(current);
        return;
    }
    for (i = num; i <= 9; i++) {
        current.add(i);
        backtracking(i + 1, current, k, n, sum + i);
        current.pop();
    }
}

call backtracking(1, [], k, n, 0);

說明：

  • 我們從 num = 1 開始遞迴探索所有可能的組合。
  • 如果總和超過 n 或數量超過 k，就提前停止（剪枝）。
  • 如果找到總和等於 n 且數量等於 k 的有效組合，就加入結果中。
  • 我們用迴圈嘗試從 num 到 9 的所有數字，確保每個數字在一個組合中只出現一次。
  • 每次遞迴呼叫結束後，我們回溯，移除最後加入的數字，以探索其他可能性。

這個方法能有效率地找出所有有效組合，同時避免不必要的計算。