class Solution(object): def combinationSum4(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ if not nums: return 0 start = min(nums) if start > target: return 0 # record number of combinations for i dp =  +  * target for i in range(len(dp)): # skip numbers that have no combinations if dp[i] != 0: for n in nums: if i + n < len(dp): dp[i + n] += dp[i] return dp[-1]
Simply share my solution. 56ms.
Man, your solution is absolutely awesome but it really took me a while to understand...
So I think it might be better if I make a clearer explanation here...
The most important trick is 'dp[i+n] += dp[i]'.
For example, let's assume target=6, nums=[1,2,3].
At some point (when i=3), the number of combination for 3 is 4 (1+1+1=3; 1+2=3; 2+1=3; 3=3).
And how to get the number of combinations for 6? Well, 6=3+3, which means we only need to add a "3" to each of the four combinations for 3: 1+1+1+3; 1+2+3, 2+1+3, 3+3.
Your might think I am missing a lot of combinations here (e.g., why 1+1+3+1 not considered? Isn't that one of the permutations for [1,1,1,3]?)
Actually, 1+1+3+1 = (1+1+3)+1 = 5+1. The '(1+1+3)+1' is just another "adding an '1' to one of the combinations for 5"
Thus, the number of combinations for i, dp[i], is based on the combinations for 0 through i-1, and dp[i]=:
(1) sum(dp[j]) (j from 1 to i-1 and i-j must in nums, if i is not in nums)
(2) sum(dp[j])+1 (j from 1 to i-1 and i-j must in nums, if i is in nums)
in the above two conditions, dp[j] must have combinations and i-j must in nums or dp[j] is skipped. (P.S.: in the second one, the extra '+1' for dp[i] could also be seen as 'adding an i to 0', so the dp was set to be 1 initially)
In our case, the final dp = [1,1,2,4,7,13,24], the number of combinations for 6 is 24. The number of combinations for 1,2,3,4,5 is 1,2,4,7,13, respectively.
We can randomly pick a number i to prove the rule in 5). Let's say i=5, for j in [1,2,3,4], i-j=4 is not in nums and i=5 is not in nums either. So dp=dp+dp+dp=2+4+7=13.
After every big for loop, only the elements in dp[:i+2] are valid. For example, when i=2, dp=2, dp=:
- [1,1,2,2,1,0,0] (before the big for loop);
- [1,1,2,4,3,2,0] (after the big for loop).
As you can see, dp, dp, dp changed +2. The 'dp[2+n] += dp' only means 'solely based on' the dp, for every combination for 2, we can 'add an 1 or 2 or 3 to the end' to respectively get additional 2 (it's 2 because dp=2) combinations for 3 or 4 or 5. So the corresponding dp, dp, dp needs to increase by dp. But until the i goes through 0~4, the dp is not valid. Also in the original code by @pushazhiniao, the 'for i in range(len(dp)):' could be changed into 'for i in range(len(dp)-1):' because the 'n' in 'i+n' is always >=1 according to the question instruction.
@hao88 Thanks, man. I changed the title of my post to hopefully clear the if statement before the second loop. This is actually a BFS under DP disguise. Because I have to know dp[i - n] for n in nums before derive dp[i] but do not want to waste time on numbers that have no possible combinations (BFS nicely avoids it), here comes the if statement to skip those.