Beating 95% Python solution using recursion with comments


  • 0

    Actually combination Sum I,II, III are very similar. We only need to modify our solution a little bit to meet the requirements. My solution for Sum II is here.

    def combinationSum3(self, k, n):
        # We don't need to sort, because each number only can be used once,
        # and all they are all positive. 
        result = []
        self.combination_sum_3(k, 1, n, [], result)
        return result
    
    def combination_sum_3(self, length, start, target, path, result):
        # In this problem, I give a property `length` to track the current length of
        # our path. We decrease the length by 1 each recursive call. So in the base 
        # case here we only need to check whether the length is 0 (the real length
        # of path is exactly 3). 
        # The design of `target` is still the same as Sum I and II.
        if not target and not length:
            result.append(path)
            return
        
        for i in xrange(start, 10):
            # Avoid unnecessary searching, since all the numbers are positive.
            if not length or i > target:
                return
    
            # We set `start` as `i + 1` because all candidates only could be 
            # used once, otherwise we set it as `i`. 
            self.combination_sum_3(length - 1, i + 1, target - i, path + [i], result)
    

  • 0

    Who ever downvoted, please add your comment


Log in to reply
 

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