Clean 0ms DP C++ Solution with good expalanation (two implementation flavors)


  • 2
    C

    This is clearly a DP problem, we need to encode the target sum value into our DP state.

    The DP state is this:

    dp[i] = the number of subsets which has sum of i. Our end goal is to compute dp[target] and the initial state is dp[0] = 1, because empty state is a valid subset and its sum is 0.

    Induction rule:

    dp[i] = dp[i - nums[0]] + dp[i - nums[1]] + ... + dp[i - nums[j]] + ...
    where j is all possible indices from [0, nums.size()-1]. And of course all out of bound i - nums[j] should be excluded in the sum.

    This problem is indeed an unbounded 1/0 knapsack problem, and identical to Problem Coin Change.

        int combinationSum4(vector<int>& nums, int target) {
            int dp[target+1];
            dp[0] = 1;
            for (int i=1; i<=target; i++) {
                dp[i] = 0;
                for (int j=0; j<nums.size(); j++) {
                    int prev = i - nums[j];
                    if (prev >= 0) dp[i] += dp[prev];
                }
            }
            return dp[target];
        }
    

    The above solution is calculating current dp[i] with all states to the left of it, actually we can also update dp[i + nums[j]] to the right of it, the dp induction rule is still the same. Like this version:

        int combinationSum4(vector<int>& nums, int target) {
            int dp[target+1];
            for (int i=0; i<=target; i++) dp[i] = 0;
            dp[0] = 1;
            for (int i=0; i<=target; i++) {
                for (int j=0; j<nums.size(); j++) {
                    int next = i + nums[j];
                    if (next <= target) dp[next] += dp[i];
                }
            }
            return dp[target];
        }
    

Log in to reply
 

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