0491. 非递减子序列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

给你一个整数数组 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

2. 🎯 s.1 - 回溯

c

int resSize;
int** res;
int* resColSizes;
int path[15];
int pathLen;

void dfs(int* nums, int numsSize, int start) {
    if (pathLen >= 2) {
        res[resSize] = (int*)malloc(sizeof(int) * pathLen);
        memcpy(res[resSize], path, sizeof(int) * pathLen);
        resColSizes[resSize] = pathLen;
        resSize++;
    }
    int used[201] = {0}; // nums[i] ∈ [-100, 100]
    for (int i = start; i < numsSize; i++) {
        if (used[nums[i] + 100]) continue;
        if (pathLen > 0 && nums[i] < path[pathLen - 1]) continue;
        used[nums[i] + 100] = 1;
        path[pathLen++] = nums[i];
        dfs(nums, numsSize, i + 1);
        pathLen--;
    }
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    res = (int**)malloc(sizeof(int*) * 100000);
    resColSizes = (int*)malloc(sizeof(int) * 100000);
    resSize = 0;
    pathLen = 0;
    dfs(nums, numsSize, 0);
    *returnSize = resSize;
    *returnColumnSizes = resColSizes;
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function (nums) {
  const res = []
  const dfs = (start, path) => {
    if (path.length >= 2) res.push([...path])
    const used = new Set()
    for (let i = start; i < nums.length; i++) {
      if (used.has(nums[i])) continue
      if (path.length && nums[i] < path[path.length - 1]) continue
      used.add(nums[i])
      path.push(nums[i])
      dfs(i + 1, path)
      path.pop()
    }
  }
  dfs(0, [])
  return res
}

py

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(start, path):
            if len(path) >= 2:
                res.append(path[:])
            used = set()
            for i in range(start, len(nums)):
                if nums[i] in used:
                    continue
                if path and nums[i] < path[-1]:
                    continue
                used.add(nums[i])
                path.append(nums[i])
                dfs(i + 1, path)
                path.pop()
        dfs(0, [])
        return res

• 时间复杂度：$O(2^n\times n)$
• 空间复杂度：$O(n)$（不计结果）

算法思路：

• 回溯枚举所有非递减子序列
• 同一层用 Set 去重，避免重复选择相同元素