Backtracking python code.


  • 0
    B
    class Solution:
        # @return a list of lists of integers
        def combine(self, n, k):
            if n==0:
                return []
            
            assert k<=n, "k is larger than number of integers"
            
            result=[]
            choice=[x for x in range(1,n+1)]
            
            def backtracking(remaining,temp,index,result):
                if remaining==0:
                    result.append(temp[:])  #need a copy
                    return
                if n-index<remaining:  # early pruning
                    return
                if not choice: # redundancy safety check
                    return
                for i in range(index,n):
                    temp.append(choice[i])
                    backtracking(remaining-1,temp,i+1,result)  # only consider elements larger than the chosen one
                    temp.pop()
                    
            backtracking(k,[],0,result)
            
            return result
    

    Only thing to mind is you need [:] copy to add your temp solution to the final result list.


Log in to reply
 

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