Share My Python Solution beating 98.17%


  • 11
    M
    class Solution(object):
    def combinationSum(self, candidates, target):
        result = []
        candidates = sorted(candidates)
        def dfs(remain, stack):
            if remain == 0:
                result.append(stack)
                return 
    
            for item in candidates:
                if item > remain: break
                if stack and item < stack[-1]: continue
                else:
                    dfs(remain - item, stack + [item])
        
        dfs(target, [])
        return result

  • 0
    B

    It's amazing that your solution is much faster than most of solutions! I will appreciate it if you could explain what's the actual meaning of your pruning ~..~, thanks


  • 5
    M

    Hello Boromir,

    Thank you for your response. I will try my best to explain my algorithm.

    1. First, I sort the candidates list. So, in the for loop, if one item in candidates in bigger than "remain" the remaining items must bigger than remain. That's why I just break the for loop.

    2. The second "if" in the for loop is for the purpose of avoiding duplicate terms and maintaining the answer in increasing order. We implement this purpose by avoiding appending items that is smaller than the last term in stack (if the stack is not empty).

    That's how I pruning. Hope I answer your question.

    Thank you!!


  • 0
    I

    combined with other people's great solutions (the top voted C++ solution), which passes down the current index of the for loop, so that we can skip the used items and don't have to check if item < stack[-1]. The improved version beats 99.04% in 79ms

    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            def dfs(remain, combo, index):
                if remain == 0:
                    result.append(combo)
                    return
                for i in range(index, len(candy)):
                    if candy[i] > remain:
                        # exceeded the sum with candidate[i]
                        break #the for loop
                    
                    dfs(remain - candy[i], combo + [candy[i]], i)
                    
            candy = sorted(candidates)
            result = []
            dfs(target, [], 0)
            return result
    

  • 0
    Z

    @ian34 why is it so fast? combo + [candy[i]] copies the tmp list for every DFS call, right? I though it would be much slower than using a shared list by calling append/pop functions


Log in to reply
 

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