DP solution in Python


  • 14
    C

    I also did it with recursion, turns out the DP solution is 3~4 times faster.

    def combinationSum2(self, candidates, target):
        candidates.sort()
        table = [None] + [set() for i in range(target)]
        for i in candidates:
            if i > target:
                break
            for j in range(target - i, 0, -1):
                table[i + j] |= {elt + (i,) for elt in table[j]}
            table[i].add((i,))
        return map(list, table[target])

  • 1
    F

    I am wondering what if I give you a input like : candidates: {1,2,3}, target: 2147483647. or any other targets which are very large.
    Just talking about some bad cases, but your solution itself is pretty smart!


  • 0
    C

    you are right, when the target is huge it takes a lot of memory with no good use!


  • 0
    W

    Neat! But I do not think this is DP enough(?) Cause there are no clear sub problems solved before the larger problems. Eg. For each iteration, this alg. updates multiple result sets. And only until the program terminated can we finally and safely get the table[target].


  • 1
    A

    Do we need to sort here? what is its purpose?


  • 0
    A

    Good solution. I got a cleaner version here.

    class Solution(object):
        def combinationSum2(self, candidates, target):
            candidates.sort()
            dp = [set() for i in xrange(target+1)]
            dp[0].add(())
            for num in candidates:
                for t in xrange(target, num-1, -1):
                    for prev in dp[t-num]:
                        dp[t].add(prev + (num,))
            return list(dp[-1])
    

    For the uninitiated, basically, this problem is a variant of the knapsack problem. If you can understand the solution to Coin Change or Coin Change 2, then you can easily understand this solution. One caveat here is that the inner loop is reversed for t in xrange(target, num-1, -1), because each number can only be used once.

    Food for thought - what happens if we don't reverse the inner loop? Can that be used to solve Combination Sum?


  • 0
    L

    @alexj Can you please explain more why inner loop needs to be reversed in order to make sure each number is used once?


Log in to reply
 

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