Python beat 100%. With deatailed comments


  • 0
    X
    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            # first we sort it. We will see why when you finish reading all the code
            nums = sorted(candidates)
            L = len(nums)
            # table[i] is a list of all possible solution if the target is i
            table = [[] for i in range(target + 1)]
            for i in range(1, target+1):
                for j in range(L):
                    num = nums[j]
                    if num > i:
                        break
                    if num == i:
                        table[i].append([num])
                    # DP substructure is presented here
                    elif table[i - num]:
                        # for each sub-solution
                        for sub in table[i - num]:
                            # this if is used for eliminating duplicate elements. This is also why we sort the candidates at first.
                            if num >= sub[-1]:
                                table[i].append(sub + [num])
            return table[target]
    

Log in to reply
 

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