当前位置：首页 > article >正文

491. 递增子序列

article 2024/9/23 19:22:06

题目描述

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

解答

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        res.clear();
        path.clear();

        backtrack(nums, 0);
        return res;
    }

    void backtrack(vector<int>& nums, int startidx)
    {
        if(path.size() > 1) // 只要临时子序列长度超过1即可作为答案加入结果集
        {
            res.push_back(path);
        }

        unordered_set<int> myset; // 用来去重防止相同元素取两次

        for(int i = startidx; i < nums.size(); ++i)
        {
            // 新元素破坏递增性或前面已经用过，则跳过该元素
            if((!path.empty() && nums[i] < path.back())
                ||myset.find(nums[i]) != myset.end()) continue;
            path.push_back(nums[i]);
            myset.insert(nums[i]);
            backtrack(nums, i + 1); // 起点后移一位进行回溯查询
            path.pop_back();
        }
    }
};