題目

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. 非遞減子序列

---

思路（注意事項）

1. 用數組記錄同一層是否有重復的元素

• !path.empty()才可以保證有path.back()。
• 至于為什么回溯的時候沒有將標記重置回0，是因為要求同一層不能有重復的元素，如果重置0，則后續元素判斷時，會忘記之前是否有與其相等的元素。

3. 用哈希表記錄同一層是否有重復的元素

---

純代碼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;}
};