39. Combination Sum

發表於 | 分類於

problem

找出所有組合總和為target 的子序列，可以重複選取，但每組組合必須唯一。

sloution

  • 用遞迴暴力求解，遍歷每種可能，終止條件target<0

  • 因為可以重複，所以每次調用bracktracking(candidates, target - candidates[i], path, ret, i) 而不是l+1。

  • version 1 

    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 bracktracking(vector<int>& candidates,int target, vector<int> & path, vector<vector<int>>& ret, int l ){
            
            if(target<0) return;
            if(target ==0){
                ret.push_back(path);
                return;
            }
            for(int i=l;i<candidates.size(); ++i){
                path.push_back(candidates[i]);
                bracktracking(candidates, target - candidates[i], path, ret, i);
                path.pop_back();
            }
            
            
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>>  ret;
            vector<int> path;
            bracktracking(candidates, target, path, ret, 0);
            return ret;
        }
    };

  • version 2 sorting 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        void bracktracking(vector<int>& candidates,int target, vector<int> & path, vector<vector<int>>& ret, int l ){
            // 終止條件
            if(target<0) return;
            if(target ==0){
                ret.push_back(path);
                return;
            }
            for(int i=l;i<candidates.size(); ++i){
                if(target - candidates[i]<0) return ; //sort
                path.push_back(candidates[i]);
                // 因為可重複拿取同一元素
                bracktracking(candidates, target - candidates[i], path, ret, i);
                path.pop_back();
            }
            
            
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end()); //sort
            vector<vector<int>>  ret;
            vector<int> path;
            bracktracking(candidates, target, path, ret, 0);
            return ret;
        }
    };

    analysis

  • time complexity O(len(nums)^M), M is the height of our recursive

  • space complexity L , L is the longest combination