Non-decreasing Subsequences Python Solution

lcpy gen -n 491   # by problem number
lcpy gen -s non_decreasing_subsequences   # by problem name

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

class Solution:
    # Time: O(2^n * n)
    # Space: O(n) recursion depth (output excluded)
    def find_subsequences(self, nums: list[int]) -> list[list[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            if len(path) >= 2:
                result.append(path.copy())
            seen: set[int] = set()
            for i in range(start, len(nums)):
                if nums[i] in seen or (path and nums[i] < path[-1]):
                    continue
                seen.add(nums[i])
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result