Dynamic Programming Solution


  • 12
    L

    It adapts the DP solution of coin change problem

    class Solution {
    public:
    	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    		vector< vector< vector<int> > > combinations(target + 1, vector<vector<int>>());
    		combinations[0].push_back(vector<int>());
    		for (auto& score : candidates)
    			for (int j = score; j <= target; j++)
    				if (combinations[j - score].size() > 0)	{
    					auto tmp = combinations[j - score];
    					for (auto& s : tmp)
    						s.push_back(score);
    					combinations[j].insert(combinations[j].end(), tmp.begin(), tmp.end());
    				}
    		auto ret = combinations[target];
    		for (int i = 0; i < ret.size(); i++)
    			sort(ret[i].begin(), ret[i].end());
    		return ret;
    	}
    };

  • 0
    H

    Can you elaborate your idea ?


  • 0
    H
    This post is deleted!

  • 4
    S

    Hnn, I use the same idea as you did. I can help illustrate the idea.

    Thinking about there is an opt[] array, each element in the array is a vector<vector<int>>.
    We do DP from opt[0] to opt[target].

    // base case

    opt[0] = [[]]

    // iteration

    opt[i] =

    1. add candidates[j] to each list in opt[i-candidates[j]] if i > candidates[j]
      .Add each list to opt[i]

    2. create candidates[j] as a new vector<int> if i == candidates[j]
      .Add this list to opt[i]


  • 0
    A

    This is just like a coin change/knapsack problem. We need to create a vector of the size of target. and for each o(1)...o(target) we get the values. and if in between we find any sum == target, add that into the result


  • 6
    V

    Sorting input first is easier

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector< vector< vector<int> > > combinations(target + 1, vector<vector<int>>());
        combinations[0].push_back(vector<int>());
        for (auto& score : candidates)
            for (int j = score; j <= target; j++){
                auto sls = combinations[j - score];
                if (sls.size() > 0) {
                    for (auto& s : sls)
                        s.push_back(score);
                    combinations[j].insert(combinations[j].end(), sls.begin(), sls.end());
                }
            }
        return combinations[target];
    }
    

  • 0
    A

    How do you avoid duplicates in this case? For example, how do you differentiate from
    [1, 2, 2, 3] and [2, 1, 2, 3]?


  • 2
    X

    Let me help illustrate the idea.

    We consider, what targets will be yielded, every time a candidate is appended to all the existing combinations.

    Here is my more understandable code using the same idea.

    vector<vector<int>> Solution::combinationSum_dp_increment(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
    
        vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>());
        dp[0].push_back(vector<int>());
    
        for (const int &candidate : candidates) {
            // all the existing combinations, except for those whose sum exceeds target
            for (int sub_target = 0; sub_target + candidate <= target; ++sub_target){  
                vector<vector<int>> new_combinations = dp[sub_target];
                for (vector<int> &new_combination: new_combinations) {  // append a candidate
                    new_combination.push_back(candidate);
                }
                int target_yielded = sub_target + candidate;  // the target yielded
                dp[target_yielded].insert(dp[target_yielded].end(), new_combinations.begin(), new_combinations.end());
            }
        }
    
        return dp[target];
    }
    

Log in to reply
 

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