Algorithm
Problem Name: 491. Non-decreasing Subsequences
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
function findSubsequences(nums) {
const res = []
helper([], 0, nums, res)
return res
}
function helper(list, index, nums, res) {
if (list.length > 1) {
res.push(Array.prototype.slice.call(list, 0))
}
const used = []
for (let i = index; i < nums.length; i++) {
if (used.indexOf(nums[i]) !== -1) {
continue
}
if (list.length === 0 || nums[i] >= list[list.length - 1]) {
used.push(nums[i])
list.push(nums[i])
helper(list, i + 1, nums, res)
list.pop()
}
}
}
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]]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findSubsequences(self, nums):
subs = {()}
for num in nums:
subs |= {sub + (num,) for sub in subs if not sub or sub[-1] <= num}
return [sub for sub in subs if len(sub) >= 2]
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]]