Non decreasing subsequences

Array Hash Table Backtracking Bit Manipulation

62.5% acceptance

Jan 13, 2026

3807

237

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;

impl Solution {
  pub fn find_subsequences(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = HashSet::new();
    Self::backtrack(&nums, 0, vec![], &mut result);
    result.into_iter().collect()
  }
  
  fn backtrack(nums: &[i32], start: usize, path: Vec<i32>, result: &mut HashSet<Vec<i32>>) {
    if path.len() >= 2 {
      result.insert(path.clone());
    }
    
    for i in start..nums.len() {
      if path.is_empty() || nums[i] >= *path.last().unwrap() {
        let mut new_path = path.clone();
        new_path.push(nums[i]);
        Self::backtrack(nums, i + 1, new_path, result);
      }
    }
  }
}