C++ 9lines, DP solution


  • 0
    J
    int combinationSum4(vector<int>& nums, int target) {
            int n = nums.size();
            vector<int> dp(target+1,0);
            dp[0] = 1;
            for(int j = 0; j <= target; ++j){   //dp[j] means ways to get sum to i
                for(int i = 0; i < n; ++i ){    // dp[k][j] = dp[k-1][j] + dp[k][j-num[k]], using "rolling array"
                    if(nums[i] <= j)    dp[j] += dp[j-nums[i]];
                }
            }
            return dp.back();
        }
    

Log in to reply
 

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