Beats 97% Python Solution

  • 0
    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:
                    elif nums[i] == curr_num:
                return combine(curr_num, choices)
            output = []
            for i in range(len(nums)):
                if i in done_set: # special optimization
                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.