代码随想录打卡—day29—【回溯】— 回溯基础练习 4.19+4.20

1 491. 非递减子序列

一开始的思路是根据上一篇的3 90. 子集 II，加上set开始魔改。

即不要nums[i]和相邻元素val相等且在同一层就continue，但是本题不能sort所以没有相邻元素val，所以我加了set设置为本层之前遍历过的元素。代码如下，但是还是过不了这样的样例。

[4,6,7,1,7,7]

[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    bool vis[300];

    void dfs(int start_idx,vector<int>& nums)
    {
        if(path.size() >= 2)ans.push_back(path);
        if(start_idx == nums.size())return;

        unordered_set<int> set_now_val;
        for(int i = start_idx; i < nums.size();i++)  // 遍历一层
        {
            if(path.empty() || nums[i] >= path[path.size()-1])
            {
                // 同一层之间去重
                if(i != 0 && !path.empty() && 
                !set_now_val.empty() && set_now_val.find(nums[i]) != set_now_val.end() && vis[nums[i] + 100] == 0)continue;

                vis[nums[i] + 100] = 1;
                path.push_back(nums[i]);
                set_now_val.insert(nums[i]);
                dfs(i+1,nums);
                vis[nums[i] + 100] = 0;
                path.pop_back();
            }
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(0,nums);
        return ans;
    }
};

// [4,6,7,1,7]