Beats 97% Python Solution


  • 0
    J
    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
    
            def combine(num, choices):
                solution = {(num,)}
                for choice in choices:
                    solution.update([x + (choice,) for x in solution if choice >= x[-1]])
                return solution
    
            done_set = set()
    
            def generate(start):
                curr_num = nums[start]
    
                choices = []
                for i in range(start + 1, len(nums)):
                    if nums[i] > curr_num:
                        choices.append(nums[i])
                    elif nums[i] == curr_num:
                        choices.append(nums[i])
                        done_set.add(i)
    
                return combine(curr_num, choices)
    
            output = []
            for i in range(len(nums)):
                if i in done_set: # special optimization
                    continue
                output.extend(list(i) for i in generate(i) if len(i) > 1)
            return output
    

    Even though we can use set to handle duplications, but the solution can be much faster by dealing with it in the very beginning.


Log in to reply
 

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