[数据结构与算法]LeetCode 491. 递增子序列--递归模拟

491. 递增子序列

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

题解

用动态数组vector把递增序列的元素下标储存下来，然后递归实现。

AC代码

class Solution {
public:
    vector<int>path[20];
    vector<vector<int>>res;
    void dfs(int x,vector<int>q,vector<int> nums)
    {
        if(q.size()>=2)
        {
            res.push_back(q);
        }
        for(int i=0;i<path[x].size();i++)
        {
            q.push_back(nums[path[x][i]]);
            dfs(path[x][i],q,nums);
            q.pop_back();
        }
    }
    static int cmp(vector<int>a,vector<int>b)
    {
        if(a.size()<b.size())
        return true;
        if(a.size()==b.size())
        {
            for(int i=0;i<a.size();i++)
            {
                if(a[i]<b[i])
                return true;
                else if(a[i]>b[i])
                return false;
            }
        }
        return false;
    }
    vector<vector<int>>res2;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[j]>=nums[i])
                path[i].push_back(j);
            }
        }
        vector<int>q;
        for(int i=0;i<nums.size();i++)
        {
            if(path[i].size()>0)
            {
                q.push_back(nums[i]);
                dfs(i,q,nums);
                q.pop_back();
            }
        }
        if(res.size()==0)
        return res;
        sort(res.begin(),res.end(),cmp);
        res2.push_back(res[0]);
        for(int i=1;i<res.size();i++)//去重复
        {
            int n=res2.size()-1;
            if(res[i]!=res2[n])
            {
                res2.push_back(res[i]);
            }
        }
        return res2;
    }
};