Iterative Python DP Solution (88.48%)


  • 0
    H
    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            dp = [[] for _ in range(target+1)]
            for i in range(target+1):
                for c in candidates:
                    if c == i:
                        dp[i] += [[c]]
                    if c < i and i-c >= c:
                        dp[i] += [[c] + partial for partial in dp[i-c] if partial[0] >= c]
            return dp[target]
    

Log in to reply
 

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