未排序数组的树层去重

491.递增子序列
reference

/* 未排序 + 树层去重
之前在进行树层去重时，我们都是先对元素排序，这样如果树层中的元素重复，
它们的位置一定是相邻的，因此我们可以通过 !st[i-1] 来判断树层元素是否重复
但现在我们不能对元素进行排序，该如何去重呢？
其实也很简单，对于树中的每一层，我们只需要用一个容器st来存放当前树层中出现的元素
这样判断的方式就成了 !st.find(i-1)
在这里，由于元素范围在[-100,100]，我们可以使用数组来作为这个容器
*/
class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        const int OFFSET = 100;
        function<void(int)> dfs = [&](int u) {
            if(path.size() > 1) res.push_back(path); // 因为题目没有限定元素的个数,所以找到合法解直接加入答案集合
            if(u == nums.size())    return ;
            bool st[210]{false};
            for(int i = u; i < nums.size(); i ++ ) {
                if(!path.empty() && nums[i] < path.back())  continue; // 不满足递增
                if(st[nums[i] + OFFSET])  continue; // 树层重复
                st[nums[i] + OFFSET] = true; // 已经出现过的元素放入容器
                path.push_back(nums[i]);
                dfs(i + 1);
                path.pop_back();
            }
        };
        dfs(0);
        return res;
    }
};