Share an iterative C++ solution


  • 0

    The basic idea is start with smallest candidate, fill every possible sum values across 1..target, record every combinations as vector<int> under certain sum.

    class Solution{
    public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> defaultValue;
        if (candidates.empty() || target < 1) {
            return defaultValue;
        }
    
        sort(candidates.begin(), candidates.end());
        vector<vector<vector<int>>> mem(target+1, vector<vector<int>>());
        vector<vector<int>> initV(1, vector<int>(1, 0));
        mem[0] = (initV);
        int n = candidates.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= target; j++){
                int sum = candidates[i] + j;
                if(sum > target){
                    break;
                }else if(mem[j].size() > 0){
                    for(int k = 0; k<mem[j].size(); k++){
                        vector<int> v(mem[j][k]);
                        v.push_back(candidates[i]);
                        mem[sum].push_back(v);
                    }
                }
            }
        }
        
        return mem[target];
    }
    

    };


Log in to reply
 

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