Question

491. 非递减子序列

English Version

题目描述

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

 

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

 

提示：

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

解法

方法一：DFS

DFS 递归枚举每个数字选中或不选中，这里需要满足两个条件：

1. 子序列需要递增（非严格递增），因此序列的后一个数要大于等于前一个数；
2. 子序列需要去重，这里重复的问题在于前后两个数相等并且不选中的情况，我们只在前后两个数不等的情况下，执行不选中的操作即可达到去重的效果。

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
}