LeetCode 491. 非递减子序列

Categories:

题目描述
思路分析
1. 解法一：回溯 + 去重（推荐）
相似题目

题目描述

✅ 491. 非递减子序列

思路分析

解法一：回溯 + 去重（推荐）

核心思路：

回溯枚举所有可能子序列，保持非递减。

每层使用集合去重，避免同层选择相同数导致重复结果。

长度至少为 2 时加入结果。

复杂度分析：

时间复杂度：O(2^n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于递归栈与路径。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int index, List<Integer> path, List<List<Integer>> res) {
        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }

        Set<Integer> used = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            if (!used.add(nums[i])) {
                continue;
            }

            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func findSubsequences(nums []int) [][]int {
	res := make([][]int, 0)
	path := make([]int, 0)

	var dfs func(start int)
	dfs = func(start int) {
		if len(path) >= 2 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
		}

		used := make(map[int]struct{})
		for i := start; i < len(nums); i++ {
			if len(path) > 0 && nums[i] < path[len(path)-1] {
				continue
			}
			if _, ok := used[nums[i]]; ok {
				continue
			}
			used[nums[i]] = struct{}{}

			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}

	dfs(0)
	return res
}

相似题目

题目	难度	考察点
78. 子集	中等	回溯
90. 子集 II	中等	回溯
47. 全排列 II	中等	回溯
40. 组合总和 II	中等	回溯
491. 非递减子序列	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/14945738