Output Limit Exceeded in python


  • 1
    S

    I always get output limit exceeded for my code. But I tested it both in eclipse and terminal, both give me the correct answers. I changed a little bit by changing "return self.result" to "return self.result[0:1]", it gives wrong result [[1,1,1]] for candidates=[1,1] target=2. But eclipse gives me [1,1], I don't know where the wrong part is. Thanks.

    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        result=[]
        temp_result=[]
        candidates=[]
    
        def combinationSum(self, candidates, target):
        	candidates=list(set(candidates))
        	self.candidates=sorted(candidates)
            if len(candidates)==0:
            	return self.result
            self.my_combination(target,0)
            return self.result
    
        def my_combination(self, target, current):
        # current is the number of candidates we need to test
            if target==0:
            	self.result.append(self.temp_result)
            	self.temp_result=list(self.temp_result)
            	self.temp_result.pop()
            else:
                for i in range(current,len(self.candidates)):
            	    if self.candidates[i]<=target:
            		    target-=self.candidates[i]
            		    self.temp_result.append(self.candidates[i])
            		    self.my_combination(target,i)
            		    target+=self.candidates[i]
                if self.temp_result!=[]:
                	self.temp_result.pop()

  • 2
    P

    I think you need to add self.result=[] and self.temp_result=[] in the beginning of the function to clean up the result of previous test case. You get [[1,1,1]] rather than [[1,1]] because last execute output for self.result is [[1]]

    def combinationSum(self, candidates, target):
        self.result=[]
        self.temp_result=[]
        candidates=list(set(candidates))
        self.candidates=sorted(candidates)
        if len(candidates)==0:
            return self.result
        self.my_combination(target,0)
        return self.result
    

    As an alternative which might introduce some more overhead, but I usually get around this issue for python on leetcode by avoiding global variables. You can see my function-level variable answer in the following example:

    class Solution:
        
        def comb(self,t,indx,max,ll,ans,pool):
    
            if t<0:
                    return
            elif t==0:
                    ans.append(ll)
                    return
            else:
                    for i in range(indx,max+1):
                            lst = ll[:]
                            lst.append(pool[i])
                            self.comb(t-pool[i],i,max,lst,ans,pool) 
    
                            
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum(self, candidates, target):
            
            candidates = list(set(candidates))
            candidates.sort()
            answer = []
            self.comb(target,0,len(candidates)-1,[],answer,candidates)
    
            return answer
    

  • 0
    J

    I'll post my solution using recursive way.
    It passed because I decrease the recursive branches.
    The code is pretty straightforward and easy to understand.

    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum(self, candidates, target):
            # occursive very obvious
            if not candidates:
                return []
            candidates = sorted(candidates)
            temp = self._combinationSum(candidates, target)
            if temp:
                return list(temp)
            
        def _combinationSum(self, candidates, target):
            if target == 0:
                yield []
            
            if target > 0:
                for i in range(len(candidates)):
                    temp = self._combinationSum(candidates[i:], target - candidates[i])
                    for s in temp:
                        yield [candidates[i]] + s

  • 0
    C

    Could you please explain why you used yield instead of return in _combinationSum()?


Log in to reply
 

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