題目網址：https://leetcode.cn/problems/combination-sum/

題意：給一無重複數的 array candidates 和一整數 target, 找出 candidates 中可以使數字和等於 target 的所有不同組合, 以任意順序返回。

其中, candidates[i] 皆 > 0

注意：candidates 同一個數字可以無限次重複選取, 如果至少一個數字的被選數量不同, 則兩種組合是不同的

Solution 1：

想法：利用 DFS + Backtracking, 其中每個元素 candidates[i] 有兩種選擇：

  • 選, 並從此位置 i 繼續選要不要重複選取

  • 不選, 從下一個位置 i + 1 的元素繼續開始

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, candidates.size(), target);
        return res;
    }

private:
    vector<int> cur;
    vector<vector<int>> res;

    void dfs(vector<int>& candidates, int i, int n, int target){
        if (target == 0) {
            res.emplace_back(cur);
            return;
        } else if (target < 0 || i == n) {
            return;
        }

        dfs(candidates, i + 1, n, target); // 不取

        // 取, 由於可重複取同一數, 故 idx 仍是從 i 開始取
        cur.emplace_back(candidates[i]);
        dfs(candidates, i, n, target - candidates[i]);
        cur.pop_back();
    }
};
  • time：$O(n \cdot 2^n)$ ➔ 每個元素都有兩種選擇, 故最多有 $2^n$ 種選擇, 而每一種選擇皆需花 $O(n)$
  • space：$O(target)$ ➔ worse case 下, dfs() 最大遞迴深度為 $O(target)$

Solution 2：

想法：同 Solution 1, 只是透過 pruning 來做優化, 一旦當前元素超過 target, 則直接跳過。for loop 中之所以沒有不取元素的部分, 是因為：

  • 若取, 則會遞迴執行 dfs(j, target - candidates[j])
  • 若不取, 則在下一輪 for loop 中 dfs(j + 1, target) 是不會有 nums[j] 的, 因為上一輪的 cur 有做 backtracking, 會將狀態還原回加入 nums[j] 前的狀態後, 才進到下一輪的 j + 1
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, candidates.size(), target);
        return res;
    }

private:
    vector<int> cur;
    vector<vector<int>> res;

    void dfs(vector<int>& candidates, int i, int n, int target){
        if (target == 0) {
            res.emplace_back(cur);
            return;
        }

        // 若要取, 則會遞迴執行；若不取, 則 for loop 迭代到 j + 1
        for (int j = i; j < n; ++j) {
            if (candidates[j] > target) {
                continue; // 剪枝, 一旦超過 target 則跳過
            }
            
            cur.emplace_back(candidates[j]);
            dfs(candidates, j, n, target - candidates[j]);
            cur.pop_back();
        }
    }
};
  • time：$O(n \cdot 2^n)$ ➔ worse case 仍為 $O(n \cdot 2^n)$, 透過使用 pruning, 實際運行情況應該是遠小於 $O(n \cdot 2^n)$ 的
  • space：$O(target)$ ➔ worse case 下, dfs() 最大遞迴深度為 $O(target)$