Backtracking Python Sol (Short Code and Easy to understand)


  • 1
    Z

    A backtracking solution to find all possible cases.
    Use hashset to remove the duplicates.
    Because list is not hashable, so I use tuple to save the current elements in each recursion.
    The time complexity is exponential for sure, but the code is relatively short.

    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            hashset = set()
            prev = -101 #numbers are in the range of [-100,100]
            self.backTrack(nums,0,(),prev,hashset)
            return list(hashset)
        
        def backTrack(self,nums,index,currTuple,prev,hashset):
            # print currList
            if len(currTuple) > 1 : hashset.add(currTuple)
            if index == len(nums) : return
            for i in range(index,len(nums)):
                if nums[i] >= prev:
                    self.backTrack(nums,i + 1,currTuple + (nums[i],),nums[i],hashset)
    

Log in to reply
 

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