Python solution DP way to do BFS 56ms


  • 2
    P
    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 = [1] + [0] * 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.


  • 2
    W

    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].

    1. 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).

    2. 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.

    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]?)

    4. 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"

    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[0] was set to be 1 initially)

    6. 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.

    7. 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[5]=dp[2]+dp[3]+dp[4]=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]=2, dp=:

    1. [1,1,2,2,1,0,0] (before the big for loop);
    2. [1,1,2,4,3,2,0] (after the big for loop).

    As you can see, dp[3], dp[4], dp[5] changed +2. The 'dp[2+n] += dp[2]' only means 'solely based on' the dp[2], 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]=2) combinations for 3 or 4 or 5. So the corresponding dp[3], dp[4], dp[5] needs to increase by dp[2]. But until the i goes through 0~4, the dp[5] 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.


  • 0
    P

    @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.


Log in to reply
 

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