Accepted recursive solution in Python


  • 1
    L

    The code recursively checked all possible candidates. Dislike the solution for the Combination Sum problem, here "self.combinationSum2(candidates[ii+1:],target-elem)" exclude the current element in the candidate list and check whether each candidate list exists in the ans list before get added in. Let me know if you have any questions.

    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum2(self, candidates, target):
            ans=[]
            candidates.sort()
            for ii,elem in enumerate(candidates):
                if target>elem:
                    subList=self.combinationSum2(candidates[ii+1:],target-elem)
                    if subList:
                        ans+=[[elem]+lis for lis in subList if [elem]+lis not in ans]
                elif target==elem:
                    if [elem] not in ans:
                        ans+=[[elem]]
                else:
                    break
            return ans

Log in to reply
 

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