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

• 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];
}
``````

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