491. Non-decreasing Subsequences
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Array、Hash Table、Backtracking、Bit Manipulation
一、題目
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
Example 1:
- Input: nums = [4,6,7,7]
- Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
- Explanation:
Example 2:
- Input: nums = [4,4,3,2,1]
- Output: [[4,4]]
Constraints:
<= nums.length <= 15-100 <= nums[i] <= 100
二、分析
- 這一很典型的是一個
backtrack的問題，只要熟悉回溯法的框架並注意終止條件與處理重覆子序列即可。 - 終止條件為
i == nums.size()，此時將遍歷過的path加入res，但要注意題目有規定至少要2個元素的子序列，故需要再加入前做確認。 - 注意題目傳回的子序列不可重覆，故需要額外做處理。
三、解題
1. Backtracking
- Time complexity: \(O(2^n)\)
- Space complexity: \(O(n)\)
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
dfs(nums, 0, path, res);
sort(res.begin(), res.end()); // 先做排序後
for (int i = res.size()-1; i >= 1; i--) { // 從後面往前迭代
if (res[i] == res[i-1]) {
res.erase(res.begin()+i); // 刪除重覆的序列
}
}
return res;
}
void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) {
if (i == nums.size()) { // 終止條件
if (path.size() > 1) { // 滿足子序列元素大於等於2個，則加入答案
res.push_back(path);
}
return;
}
if (path.size() == 0 || nums[i] >= path.back()) { // 注意需滿足題意為上升序列
path.push_back(nums[i]); // 加入子序列
dfs(nums, i+1, path, res);
path.pop_back(); // 回溯法需將元素 pop 掉
}
dfs(nums, i+1, path, res); // 跳過不取
}2. Backtracking(optimized)
- Time complexity: \(O(2^n)\)
- Space complexity: \(O(n)\)
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
dfs(nums, 0, path, res);
return res;
}
void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) {
if (i == nums.size()) {
if (path.size() > 1) {
res.push_back(path);
}
return;
}
if (path.size() == 0 || nums[i] >= path.back()) {
path.push_back(nums[i]);
dfs(nums, i+1, path, res);
path.pop_back();
}
if (path.size() == 0 || nums[i] != path.back()) { // 處理重覆子序列
dfs(nums, i+1, path, res);
}
}