回溯算法--递增子序列
输入：nums = [4,4,3,2,1]输出：[[4,4]]
注意点
- 此题目的集合是无序的，并且要求同一层之间的去重，因此和之前有序的同一层去重（used数组）不同，千万不能混淆。
- 此题还需要对保证输出的组合是有序的，因此怎么保证path是有序的。
思路
- 无序集合的树层之间去重，可以使用unordered_set,记录每一层出现过的元素，在for循环之前定义，一个for循环是一层，因此要在for循环之前定义。并且每一层都单独需要一个unorered_set来记录每一层是否重复，因此不需要对unordered_set进行回溯。
- 要保证有序，就是要保证正在访问的元素nums[i] > path数组中最后一个元素，path.back可以表示最后一个元素。但是使用back要保证nums数组不能为空。
代码
回溯三部曲，
参数
void backtracking(const vector<int>& nums, int startIndex)终止条件
其实也可以不需要终止条件，因为递归会一直遍历，一直寻找合适的path，即走完所有的for循环自动停止。
if (path.size() > 1) { result.push_back(path); } // 终止条件2：如果路径长度等于原数组长度，不再继续（虽然这种情况很少） if (path.size() == nums.size()) return;单层循环逻辑
- 为什么unordered_set创建的位置在for循环之前
- 为什么unordered_set不需要回溯
- nums.back使用的前提
- 为什么if条件里面的剪枝操作是或的关系
- 为什么是continue而不是break
// 关键：unordered_set用于记录本层元素是否重复使用 // 注意：这个uset的生命周期只在本层递归中，每次进入新的递归层都会重新定义 unordered_set<int> uset; // 遍历从startIndex开始的所有可能选择 for (int i = startIndex; i < nums.size(); i ++) { // 剪枝条件1：如果当前元素小于路径最后一个元素，跳过（不满足递增） // 注意：需要先检查path是否为空，否则path.back()会出错 // 剪枝条件2：如果当前元素在本层已经使用过，跳过（去重） // 注意：这里的去重是针对同一递归层，不是针对整个递归树 if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue; uset.insert(nums[i]); path.push_back(nums[i]); // 递归：从i+1开始继续寻找（注意是i+1，不是i，因为不能重复使用同一索引的元素） backtracking(nums, i + 1); path.pop_back(); // 注意：uset不需要撤销，因为它在栈上，每次递归会重新创建 }整体代码
class Solution { private: vector<vector<int>> result; // 存储所有递增子序列的结果 vector<int> path; // 存储当前正在构建的递增子序列 // 回溯函数：寻找所有递增子序列 // nums: 输入数组 // startIndex: 当前递归开始选择的起始索引 void backtracking(const vector<int>& nums, int startIndex) { // 终止条件1：当路径长度大于等于2时，保存当前递增子序列 // 题目要求子序列长度至少为2 if (path.size() > 1) { result.push_back(path); } // 终止条件2：如果路径长度等于原数组长度，不再继续（虽然这种情况很少） if (path.size() == nums.size()) return; // 关键：unordered_set用于记录本层元素是否重复使用 // 注意：这个uset的生命周期只在本层递归中，每次进入新的递归层都会重新定义 unordered_set<int> uset; // 遍历从startIndex开始的所有可能选择 for (int i = startIndex; i < nums.size(); i ++) { // 剪枝条件1：如果当前元素小于路径最后一个元素，跳过（不满足递增） // 注意：需要先检查path是否为空，否则path.back()会出错 // 剪枝条件2：如果当前元素在本层已经使用过，跳过（去重） // 注意：这里的去重是针对同一递归层，不是针对整个递归树 if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue; uset.insert(nums[i]); path.push_back(nums[i]); // 递归：从i+1开始继续寻找（注意是i+1，不是i，因为不能重复使用同一索引的元素） backtracking(nums, i + 1); path.pop_back(); // 注意：uset不需要撤销，因为它在栈上，每次递归会重新创建 } } public: vector<vector<int>> findSubsequences(vector<int>& nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };