My easy understanding DP solution (C++)


  • 7
    O

    Hi, here is my dp solution. The idea is pretty similar with the dp solution of subset. :)

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        int size = candidates.size();
        if (size == 0) return result;
        sort(candidates.begin(), candidates.end());
        vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>());
        dp[0].push_back(vector<int>());
        
        for (int i = 1; i <= target; ++i) {
            for (int j = 0; j < size && candidates[j] <= i; ++j) {
                for (int k = 0; k < dp[i - candidates[j]].size(); ++k) {
                    vector<int> temp = dp[i - candidates[j]][k];
                    if (temp.size() && (temp[temp.size() - 1] > candidates[j])) continue;
                    temp.push_back(candidates[j]);
                    dp[i].push_back(temp);
                }
            }
        }
        return dp[target];
    }

  • 0
    S

    it is a nice answer!


  • 0
    X

    this kind of DP method is slow here, because it calculates too many unnecessary/unused intermediate targets


Log in to reply
 

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