Question

491. Non-decreasing Subsequences

中文文档

Description

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

Solution 1

class Solution:
  def findSubsequences(self, nums: List[int]) -> List[List[int]]:
    def dfs(u, last, t):
      if u == len(nums):
        if len(t) > 1:
          ans.append(t[:])
        return
      if nums[u] >= last:
        t.append(nums[u])
        dfs(u + 1, nums[u], t)
        t.pop()
      if nums[u] != last:
        dfs(u + 1, last, t)

    ans = []
    dfs(0, -1000, [])
    return ans

class Solution {
  private int[] nums;
  private List<List<Integer>> ans;

  public List<List<Integer>> findSubsequences(int[] nums) {
    this.nums = nums;
    ans = new ArrayList<>();
    dfs(0, -1000, new ArrayList<>());
    return ans;
  }

  private void dfs(int u, int last, List<Integer> t) {
    if (u == nums.length) {
      if (t.size() > 1) {
        ans.add(new ArrayList<>(t));
      }
      return;
    }
    if (nums[u] >= last) {
      t.add(nums[u]);
      dfs(u + 1, nums[u], t);
      t.remove(t.size() - 1);
    }
    if (nums[u] != last) {
      dfs(u + 1, last, t);
    }
  }
}

class Solution {
public:
  vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> t;
    dfs(0, -1000, t, nums, ans);
    return ans;
  }

  void dfs(int u, int last, vector<int>& t, vector<int>& nums, vector<vector<int>>& ans) {
    if (u == nums.size()) {
      if (t.size() > 1) ans.push_back(t);
      return;
    }
    if (nums[u] >= last) {
      t.push_back(nums[u]);
      dfs(u + 1, nums[u], t, nums, ans);
      t.pop_back();
    }
    if (nums[u] != last) dfs(u + 1, last, t, nums, ans);
  }
};

func findSubsequences(nums []int) [][]int {
  var ans [][]int
  var dfs func(u, last int, t []int)
  dfs = func(u, last int, t []int) {
    if u == len(nums) {
      if len(t) > 1 {
        ans = append(ans, slices.Clone(t))
      }
      return
    }
    if nums[u] >= last {
      t = append(t, nums[u])
      dfs(u+1, nums[u], t)
      t = t[:len(t)-1]
    }
    if nums[u] != last {
      dfs(u+1, last, t)
    }
  }
  var t []int
  dfs(0, -1000, t)
  return ans
}