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

  • 2

    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 = []
                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 
                        return ans
                return ans

  • -1

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

Log in to reply

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