runtime 3 ms, beats 98.16% of cpp submissions
O(2^k) solution with explanation

tags: backtracking

Combination Sum

📖 description

給定一個沒有重複元素的陣列 candidates 與 target ，回傳所有從 candidates 組合出 target 的方法，可以重複從 candidates 拿取元素。

ex.
    Input: candidates = [2,3,6,7], target = 7

    Output: [[2,2,3],[7]]

    Explanation:
    2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
    7 is a candidate, and 7 = 7.
    These are the only two combinations.

🧠 solution

利用回朔的方法，維護一個拿取元素的陣列，如果滿足所有元素的總和是 target ，就把陣列存進答案中。

在回朔的狀態中，我們可以選擇要不要拿當前看到的元素

  • 如果不拿，下一個狀態要從下一個元素拿起 (index+1)
  • 如果拿了，下一個狀態還是可以拿當前的元素 (index)

⏳ time complexity

對於每個元素 candidates[i] ，我們最多拿取 target / candidates[i] 次
定義 k 為 target / candidates[i] 的總和 (對所有 candidates 的元素計算)
則時間複雜度為 O(2^k) ，因為我們要決定哪些元素拿或不拿，而總共有 k 個元素需要考慮
總時間複雜度 O(2^k)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void re(vector<int>& c,vector<int>& now, vector<vector<int>>& ans, int r, int ind){
        if(ind>=c.size()) return;   // 如果已經沒有下一個元素
        if(r==0){                   // remain 為 0 ，表示找到答案
            ans.emplace_back(now);
        }
        else if(r<0){               // 如果 remain 已經小於 0 ，不繼續拿
            return;
        }
        else{
            now.emplace_back(c[ind]);   // 紀錄當前節點
            re(c,now,ans,r-c[ind],ind);
            now.pop_back();             // 退出當前節點
            re(c,now,ans,r,ind+1);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& c, int t) {
        vector<vector<int>> ans;
        vector<int> now;
        re(c,now,ans,t,0);
        return ans;
    }
};