【练习】【类似于子集问题】力扣491. 非递减子序列/递增子序列
题目
- 非递减子序列
给你一个整数数组 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]]
来源：力扣491. 非递减子序列
思路（注意事项）
- 用数组记录同一层是否有重复的元素
!path.empty()才可以保证有path.back()。- 至于为什么回溯的时候没有将标记重置回0，是因为要求同一层不能有重复的元素，如果重置0，则后续元素判断时，会忘记之前是否有与其相等的元素。
- 用哈希表记录同一层是否有重复的元素
纯代码1
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
void backtracking (vector<int>& nums, int start)
{
if (path.size() >= 2) ans.push_back(path);
vector<int> tmp(201, 0); // [-100,100]
for (int i = start; i < nums.size(); i ++)
{
if (!path.empty() && nums[i] < path.back() || tmp[100 + nums[i]] == 1) continue;
tmp[100 + nums[i]] = 1;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking (nums, 0);
return ans;
}
};
题解1（加注释）
class Solution {
private:
vector<vector<int>> ans; // 存储所有符合条件的子序列
vector<int> path; // 存储当前递归路径中的子序列
// 回溯函数，用于生成所有非递减子序列
void backtracking(vector<int>& nums, int start) {
// 如果当前路径中的子序列长度大于等于 2，将其加入结果
if (path.size() >= 2) ans.push_back(path);
// 使用临时数组 tmp 去重，确保同一层级中不会重复选择相同的元素
vector<int> tmp(201, 0); // 数组大小为 201，覆盖范围 [-100, 100]
// 遍历数组，从 start 开始
for (int i = start; i < nums.size(); i++) {
// 如果 path 不为空且当前元素小于 path 的最后一个元素，跳过（确保子序列非递减）
// 或者当前元素已经在本层级使用过，跳过（去重）
if (!path.empty() && nums[i] < path.back() || tmp[100 + nums[i]] == 1) continue;
// 标记当前元素为已使用
tmp[100 + nums[i]] = 1;
// 将当前元素加入路径
path.push_back(nums[i]);
// 递归调用，处理下一个元素
backtracking(nums, i + 1);
// 回溯：移除当前元素，尝试其他可能性
path.pop_back();
}
}
public:
// 主函数，生成所有非递减子序列
vector<vector<int>> findSubsequences(vector<int>& nums) {
// 从索引 0 开始回溯
backtracking(nums, 0);
// 返回所有符合条件的子序列
return ans;
}
};
纯代码2
class Solution {
private:
vector<vector<int>> ans;
vector<int> path;
void backtracking (vector<int>& nums, int start)
{
if (path.size() >= 2) ans.push_back(path);
unordered_set<int> st;
for (int i = start; i < nums.size(); i ++)
{
if (!path.empty() && nums[i] < path.back() || st.find (nums[i]) != st.end()) continue;
st.insert (nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking (nums, 0);
return ans;
}
};
题解2（加注释）
class Solution {
private:
vector<vector<int>> ans; // 存储所有符合条件的子序列
vector<int> path; // 存储当前递归路径中的子序列
// 回溯函数，用于生成所有非递减子序列
void backtracking(vector<int>& nums, int start) {
// 如果当前路径中的子序列长度大于等于 2，将其加入结果
if (path.size() >= 2) ans.push_back(path);
// 使用哈希集合 st 去重，确保同一层级中不会重复选择相同的元素
unordered_set<int> st;
// 遍历数组，从 start 开始
for (int i = start; i < nums.size(); i++) {
// 如果 path 不为空且当前元素小于 path 的最后一个元素，跳过（确保子序列非递减）
// 或者当前元素已经在本层级使用过，跳过（去重）
if (!path.empty() && nums[i] < path.back() || st.find(nums[i]) != st.end()) continue;
// 将当前元素加入哈希集合，标记为已使用
st.insert(nums[i]);
// 将当前元素加入路径
path.push_back(nums[i]);
// 递归调用，处理下一个元素
backtracking(nums, i + 1);
// 回溯：移除当前元素，尝试其他可能性
path.pop_back();
}
}
public:
// 主函数，生成所有非递减子序列
vector<vector<int>> findSubsequences(vector<int>& nums) {
// 从索引 0 开始回溯
backtracking(nums, 0);
// 返回所有符合条件的子序列
return ans;
}
};