(New Record!) 60 ms Python recursive code with an important explanation


  • 2
    H

    The idea is to avoid duplicates by picking a new different value in the while loop. This idea is similar to the Three Sum Problem.

    class Solution(object):
            def combinationSum2(self, cand, target):
                """
                :type cand: List[int]
                :type target: int
                :rtype: List[List[int]]
                """
                ans = []
                cand.sort()
                ans = self.combSumHelper(cand, target, 0)
                return ans
                
            def combSumHelper(self, cand, target, start):
                ans = []
                L = len(cand)
                i = start
                while i < L:
                    curN = cand[i]
                    newTarget = target-curN
                    if newTarget > 0:
                        result = self.combSumHelper(cand, newTarget, i+1)
                        ans += [[curN]+ele for ele in result]
                        i += 1
                        while i<L and cand[i]==curN: #avoid duplicates
                            i += 1
                    elif newTarget == 0:
                        ans += [[curN]]
                        return ans 
                    else:
                        return ans
                return ans

  • -1
    W

    ans += [[curN]+ele for ele in result]
    error


Log in to reply
 

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