C++ Non-recursive, non-duplicate, DP solution (rare for this problem)


  • 0
    A

    Couldn't find a post with a proper DP solution for this problem. Almost everyone is using simple recursive.
    Not a fan of recursive. Haven't employed any recursive to solve leetcode problems, and don't plan to.
    Here even with DP we do not generate duplicate combinations in the first place.

    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<vector<int>> dp[target+1];
            dp[0].push_back({});
            for (int i = candidates.size()-1, p = 0; i >= 0; i--) {
                int d = candidates[i] == p ? d + 1 : 0;
                p = candidates[i];
                for (int j = target; j >= p; j--) {
                    for (int k = j - p, m = dp[k].size()-1; m >= 0; m--) {
                        if (d && (dp[k][m].size() < d || *(dp[k][m].end()-d) != p)) continue;
                        dp[j].push_back(dp[k][m]);
                        dp[j].rbegin()->push_back(p);
                    }
                }
            }
            return dp[target];
        }
    };
    

  • 0
    D

    @ayuanx Please could you explain the logic?


Log in to reply
 

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