A summary of all combination sum problem in LC, C++


  • 5

    Solutions

    Primitive

    test

    • try each number and then to the next level with target chopped off by the number;
    • since we can use the number unlimited times, which means as long as we don't traverse back, it will be okay;
    • once the target is equal to zero, we get it and we can collect the stack.
    class Solution {
    private:
        int size;
        void search(vector<int>& candidates, int pos, int target, vector<int>& v, vector<vector<int>>& vv) {
            if(target < 0) return;
            if(target == 0) { vv.push_back(v); return ; }
            for(int i = pos; i < size; ++i) {
                v.push_back(candidates[i]);
                search(candidates, pos, target-candidates[i], v, vv);
                v.pop_back();
            }
        }
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            size = candidates.size();  
            vector<int> v;
            vector<vector<int>> vv;
            search(candidates, 0, target, v, vv);
            return vv;
        }
    };
    

    Follow-up 1

    test

    • each number can only be used once, so label the position and move forward one step each time;
    • there are only k numbers in a combination, so update the k properly each time;
    class Solution {
    private:
        void search(int n, int pos, int k, vector<int>& v, vector<vector<int>>& vv) {
            if(n < 0) return ;
            if(k == 0) { if(n == 0) vv.push_back(v); return ;}
            for(int i = pos; i < 10; ++i) {
                v.push_back(i);
                search(n-i, i+1, k-1, v, vv);
                v.pop_back();
            }
        }
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<int> v;
            vector<vector<int>> vv;
            search(n, 1, k, v, vv);
            return vv;
        }
    };
    

    Follow-up 2

    test

    • since we can use the number only once, so we have to move forward by one each time;
    • to avoid duplicate set, we have to avoid try the same number in the same recursive level;
    class Solution {
    private:
        int size;
        vector<vector<int>> vv;
        void search(vector<int>& candidates, int pos, int target, vector<int>& v, vector<vector<int>>& vv) {
            if(target < 0) return;
            if(target == 0) { vv.push_back(v); return ; }
            for(int i = pos; i < size; ++i) {
                if(i==pos || candidates[i]!=candidates[i-1]) {
                    v.push_back(candidates[i]);
                    search(candidates, i+1, target-candidates[i], v, vv);
                    v.pop_back();
                }
            }
        }
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            size = candidates.size();  
            vector<int> v;
            search(candidates, 0, target, v);
            return vv;
        }
    };
    

    Follow-up 3

    test

    • recursive backtracking is okay but inefficient, so we have to adopt Memoization;
    • using map is for better robustness, while an array also does and can be more efficient.
    class Solution {
    private:
        unordered_map<int, int> map;
    public:
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            if(map.count(target)) return map[target];
            long count = 0;
            for(int i = 0; i < nums.size(); ++i)
                count += combinationSum4(nums, target-nums[i]);
            return map[target] = count;
        }
    };
    
    • actually we can do better using DP.
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            int arr[target+1]{1, 0};
            for(int i = 1, size = nums.size(); i <= target; ++i)
                for(int j = 0; j < size; ++j)
                    if(i>=nums[j]) arr[i] += arr[i-nums[j]];
            return arr[target];
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.