Skip to content

491. Non Decreasing Subsequences

Array Hash Table Backtracking Bit Manipulation

Problem - Non Decreasing Subsequences

Medium

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

 

Example 1:

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]]

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(i, last, temp):
            if i == len(nums):
                if len(temp) > 1:
                    result.append(temp[:])
                return

            if nums[i] >= last:
                temp.append(nums[i])
                dfs(i + 1, nums[i], temp)
                temp.pop()

            if nums[i] != last:
                dfs(i + 1, last, temp)


        dfs(0, -101, [])
        return result

Submission Stats:

  • Runtime: 14 ms (96.00%)
  • Memory: 23.6 MB (93.19%)