https://leetcode.cn/problems/non-decreasing-subsequences/description/

<aside> 💡

这题不能对原序列进行排序，所以选择使用哈希表进行去重

注意子序列在原数组中不需要连续，所以当不满足条件是使用continue而不是break

</aside>

set

vector<vector<int>> ans;
vector<int> path;

void backtracking(int startIndex, vector<int>& nums) {
		if (path.size() >= 2)
				ans.push_back(path);
		
		// 每层设置一个set来进行树层去重
		// 由于本题nums元素有限定范围，所以也可以使用数组来进行哈希映射
		unordered_set<int> record;
		for (int i = startIndex; i < nums.size(); ++i) {
	      // 第一次使用该值 且 该元素可以组成非递减序列
				if (record.find(nums[i]) == record.end() && (path.empty() || nums[i] >= path.back())) {
						record.insert(nums[i]);
						path.push_back(nums[i]);
						backtracking(i + 1, nums);
						path.pop_back();
				}
		}
}

// 这题不能先排序
vector<vector<int>> findSubsequences(vector<int>& nums) {
		backtracking(0, nums);
		return ans;
}

数组

vector<int> cur;
vector<vector<int>> ans;

void backtracking(int pos, vector<int>& nums) {
    if (cur.size() >= 2) {
        ans.push_back(cur);
    }

    // 使用哈希表进行去重，nums元素有范围限制，所以使用vector作为容器
    vector<int> st(201, 0);
    for (int i = pos; i < nums.size(); ++i) {
        // 非递增 或 本层已经使用过该元素
        if ((!cur.empty() && nums[i] < cur.back()) || st[nums[i] + 100]) {
            continue;
        }
        cur.push_back(nums[i]);
        st[nums[i] + 100] = 1;
        backtracking(i + 1, nums);
        cur.pop_back();
    }
}

vector<vector<int>> findSubsequences(vector<int>& nums) {
    backtracking(0, nums);
    return ans;
}