491. 非递减子序列
491. 非递减子序列
https://leetcode.cn/problems/non-decreasing-subsequences/
题目描述：
给你一个整数数组 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]]
-100 <= nums[i] <= 100
思路分析：
注意，本题不能像算法练习第24天|78.子集、 90.子集II-CSDN博客中的90.子集II那样对元素组进行排序已达到元素子序列去重的目的，可以看上面的示例2，如果我们按照90题那样的做法对原数组进行排列的话【1，2，3，4，4】，就会得出不止一个非递减子序列，这显然与题目输出的【4，4】不符合。所以我们不能对原序列进行排序。
本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。
为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：
按照正常的前后顺序进行搜索，会发现两种情况下元素是不能记录的：
（1）如果当前元素比刚刚记录的元素小，那么当前元素就不能往path中添加，因为此时不符合非递减的性质。
（2）同一父节点下的那一层遍历，如果元素之前用过，那么也不能向path中添加。
上面两种情况任意一种发生，path就不能记录当前元素。所以这两种情况对应代码的逻辑关系是或||。
下面开始日常的回溯三部曲：
第一步：确认回溯函数的参数与返回值。由于需要在一个集合里面取序列，所以要用到startIndex.
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int> & nums, int startIndex){}第二步：确认回溯终止条件。当startIndex达到nums.size()之后就遍历完了，return。
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int> & nums, int startIndex){
if(startIndex == nums.size()){
return;
}第三步：确认单层遍历逻辑。此时就要考虑到我们当前的元素nums[i]是否是上面所述的两种不能记录的情况了。条件（1）如果当前元素比刚刚记录的元素小，用(!path.empty() && nums[i] < path.back())表示；条件（2）同一父节点下该元素（数值）之前用过，用used_numbers[nums[i]+100] == 1表示。
因为题目提示了nums所有元素-100 <= nums[i] <= 100，所以我们使用一个used_numbers数组来记录元素是否用过。由于数组的下标是从0开始算的，所以我们将nums[i]+100，将元素的范围【-100，100】线性拉伸到【0，200】，总共201个数。例如，当前元素为-100时，它存在数组的开始处，当元素为-99时，它存在数组的下标1处，依次类推。使用了该元素，则对应元素置1。另外也可以用set来记录用过的数据。
int used_numbers[201] = {0}; //记录统一父节点下哪些数字是用过的
for(int i = startIndex; i < nums.size(); i++){
if((!path.empty() && nums[i] < path.back())
|| used_numbers[nums[i]+100] == 1)
continue;
//不满足if条件则表示该节点可以记录，那么记录当前节点
path.push_back(nums[i]);
//判断path长度是否大于等于2，如果是，则reslut记录
if(path.size() > 1){
result.push_back(path);
}
//-100到100映射到0-201
used_numbers[nums[i]+100] = 1; //用过该数字，标志为置1
//因为子序列最少要有两个元素，所以我们平常的result.push_back(path)就不能直接写了
//result.push_back(path);
backTracking(nums, i+1);
path.pop_back();
}整体代码如下：
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int> & nums, int startIndex){
if(startIndex == nums.size()){
return ;
}
int used_numbers[201] = {0}; //记录统一父节点下哪些数字是用过的
for(int i = startIndex; i < nums.size(); i++){
if((!path.empty() && nums[i] < path.back())
|| used_numbers[nums[i]+100] == 1)
continue;
//记录当前节点
path.push_back(nums[i]);
if(path.size() > 1){
result.push_back(path);
}
//-100到100映射到0-201
used_numbers[nums[i]+100] = 1; //用过该数字，标志为置1
//因为子序列最少要有两个元素，所以我们平常的result.push_back(path)就不能直接写了
//result.push_back(path);
backTracking(nums, i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backTracking(nums, 0);
return result;
}
};下面是使用unordered_set<int>来记录重复元素的写法：
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int> & nums, int startIndex){
if(startIndex == nums.size()){
return ;
}
unordered_set<int> used_numbers; //记录统一父节点下哪些数字是用过的
for(int i = startIndex; i < nums.size(); i++){
if((!path.empty() && nums[i] < path.back())
|| used_numbers.find(nums[i]) != used_numbers.end())
continue;
//记录当前节点
path.push_back(nums[i]);
if(path.size() > 1){
result.push_back(path);
}
//-100到100映射到0-201
used_numbers.insert(nums[i]); //用过该数字，标志为置1
//因为子序列最少要有两个元素，所以我们平常的result.push_back(path)就不能直接写了
//result.push_back(path);
backTracking(nums, i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backTracking(nums, 0);
return result;
}
};注意：不管是使用数组还是set来存放使用过的数字，它们都只存在与当前递归层，即下一层的递归中数组和set都会重新创建并初始化，然后for循环在同一层中遍历，这就保证了同一父节点下可以查找元素使用已经用过。
另外，在使用set时，程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且每次重新定义set，insert的时候其底层的符号表也要做相应的扩充，也是费事的。使用数组程序还快一些。算法训练第5天|哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和-CSDN博客
在上面这篇博文349题中，提到了数组和set作为哈西表时各自的应用场景：
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费，优先使用set和map。数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组。
