Problem statement

https://leetcode.com/problems/increasing-subsequences/

Solution

One solution is to use dynamic programming, where in dp[i] we keep all sequences, which stops with element number i. In the end we need to select only sequences with length more than 1 and remove duplicates.

Complexity

Time complexity is potentially O(2^n) for non-decreasing sequence and space complexity is O(n * 2^n).

Code

class Solution:
    def findSubsequences(self, nums):
        n = len(nums)
        dp = [[[nums[i]]] for i in range(n)]
        for j, k in combinations(range(n), 2):
            if nums[j] <= nums[k]:
                for sols in dp[j]:
                    dp[k].append(sols + [nums[k]])
                        
        q = list(chain(*dp))
        return [list(s) for s in set(tuple(s) for s in q if len(s) > 1)]

Remark

There is another classical dfs+backtracking solution, where we use dfs(last, path) function, where last is the last taken index and path is sequence constructed so far. However we still need to check for duplicates.