非递减子序列 | LeetCode-491 | 回溯算法

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧！

回溯算法练习题

---

LeetCode链接：491. 非递减子序列

---

1.题目描述

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

2.1 回溯算法-哈希集合

class Solution {
    // 存储最终结果的列表，用于保存所有满足条件的子序列
    List<List<Integer>> result = new ArrayList<>();
    // 存储当前子序列的路径，用于构建每一个子序列
    List<Integer> path = new ArrayList<>();

    // 主方法 findSubsequences，输入一个整数数组 nums，返回所有递增的子序列
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 从索引 0 开始回溯生成子序列
        backtracking(nums, 0);
        // 返回生成的所有递增子序列
        return result;
    }

    // 回溯算法，用于生成所有符合条件的子序列
    public void backtracking(int[] nums, int start) {
        // 当当前路径长度大于1时，将其加入结果列表中（子序列长度至少为2）
        if (path.size() > 1) result.add(new ArrayList<>(path));

        // 使用 Set 集合去重，避免在同一层次中使用相同的元素
        Set<Integer> set = new HashSet<>();

        // 遍历数组，从起始索引开始
        for (int i = start; i < nums.length; i++) {
            // 剪枝：跳过不符合递增条件或在同一层中已处理过的数字
            // 1. 如果当前数字小于路径中的最后一个数字，则跳过（不满足递增条件）
            // 2. 如果当前数字在本轮递归中已经使用过，则跳过
            if ((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || set.contains(nums[i])) continue;

            // 将当前数字加入 Set 集合，表示本层已经处理过该数字
            set.add(nums[i]);
            // 将当前数字加入子序列路径
            path.add(nums[i]);
            // 递归处理后续的数字，构建新的子序列
            backtracking(nums, i + 1);
            // 回溯：移除路径中的最后一个元素，进行下一个可能的选择
            path.remove(path.size() - 1);
        }
    }
}

2.2 回溯算法-哈希数组

class Solution {
    // 存储最终结果的列表，用于保存所有满足条件的子序列
    List<List<Integer>> result = new ArrayList<>();
    // 存储当前子序列的路径，用于构建每一个子序列
    List<Integer> path = new ArrayList<>();

    // 主方法 findSubsequences，输入一个整数数组 nums，返回所有递增的子序列
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 从索引 0 开始回溯生成子序列
        backtracking(nums, 0);
        // 返回生成的所有递增子序列
        return result;
    }

    // 回溯算法，用于生成所有符合条件的子序列
    public void backtracking(int[] nums, int start) {
        // 当当前路径长度大于1时，将其加入结果列表中（子序列长度至少为2）
        if (path.size() > 1) result.add(new ArrayList<>(path));

        // 创建哈希数组，范围为 [-100, 100]，用于去重
        boolean[] hash = new boolean[201];

        // 遍历数组，从起始索引开始
        for (int i = start; i < nums.length; i++) {
            // 剪枝：跳过不符合递增条件或在同一层中已处理过的数字
            // 1. 如果当前数字小于路径中的最后一个数字，则跳过（不满足递增条件）
            // 2. 如果当前数字在本轮递归中已经使用过（即哈希数组中标记为 true），则跳过
            if ((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || hash[nums[i] + 100]) continue;

            // 将当前数字标记为已使用
            hash[nums[i] + 100] = true;
            // 将当前数字加入子序列路径
            path.add(nums[i]);
            // 递归处理后续的数字，构建新的子序列
            backtracking(nums, i + 1);
            // 回溯：移除路径中的最后一个元素，进行下一个可能的选择
            path.remove(path.size() - 1);
        }
    }
}