# 6 lines C++ DP solution

• result[i] is the possible combination of i.

``````    int combinationSum4(vector<int>& nums, int target) {
vector<int> result(target + 1);
result[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int x : nums) {
if (i >= x) {
result[i] += result[i - x];
}
}
}

return result[target];
}
``````

• I often find people use result[0]=1 or dp[0]=1 here . While I understand why people have done that , still think it's a bit misleading by giving the impression "the number of possible combination is 1 when the target is 0 " ...

• a bit misleading by giving the impression "the number of possible combination is 1 when the target is 0 "

The empty combination does have sum 0.

• @StefanPochmann right, it should be included in the test set. Right now it's not included. @1337c0d3r - you might want to fix that.

• @agave maybe it's not necessary, since the requirement says " find the number of possible combinations that add up to a positive integer target." , 0 is not a positive target.

• @StefanPochmann it's a bit controversial. Given nums {1,2,3} and target 0 (although it shouldn't be 0 coz the target should be positive), I would return 0 , instead of 1 :-)

• @vogelkaka What's controversial? The empty sum having value zero is standard.

• @StefanPochmann Yes , but is the empty set {} counted as "one possible combination from the original array" ? Given the example nums{1,2,3} and target 0 , the answer 0 would make more sense to me, since you can't find any possible combinations from the array which give you the sum of 0 (unless you count the empty set )

• @vogelkaka Why would the empty set (or rather, the empty combination) not count?

• How does this program rule out all the duplicate combinations? I found that amazing but hard to explain.

• @StefanPochmann Of course empty set is a sub-set of any set/array . I just find it's a bit weird to count it as an answer to the example "nums{1,2,3} and target 0" , since the empty set does not 'combine' anything from the original array. Take another example nums{0,1,2,3} and target 0 , should I return 1 , or 2 ? I guess I would ask the interviewer what to return for these cases.

• @StefanPochmann 4 - {1,1,1} , {1,2}, {2,1}, {3}

• {3}

What got "combined" there? And with what?

• @StefanPochmann 3 is from the original array, isn't it ?

• @vogelkaka Yes. So?

• @StefanPochmann so it contains at least 1 element from the original array , while the empty set contains nothing. Maybe I should've changed "combine" to "contain" to make my point clearer.

• Maybe I should've changed "combine" to "contain" to make my point clearer.

But the word "combine" and nothing getting combined was your entire argument. Where does "contain" come from, and the requirement that the combinations contain something? As far as I can see, not from the problem statement, not from mathematics, and not from computer science.

• @StefanPochmann let's assume 0 is allowed in the array and could be a valid target, consider following two cases :

1. nums empty {} and target 0
2. nums {0} and target 0

Running the code above from @Hunter37 gives answer 1 for both cases. So it seems empty set is counted in case 1 , but not in case 2 ?

• @vogelkaka

1. nums empty {} and target 0

There's one combination, namely the empty one.

1. nums {0} and target 0

There are infinitely many combinations. That's a severe change of the problem. It's not even clear what to output, as infinity isn't an `int`. The problem statement would need to specify. And you can't just take @Hunter37's solution as reference for a problem it wasn't written for.

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