32 lines
1.1 KiB
C++
32 lines
1.1 KiB
C++
#include "s0491_non_decreasing_subsequences.hpp"
|
|
|
|
void findSubsequencesDFS(vector<int> &subsequences, vector<vector<int>> &result,
|
|
vector<int> &nums, int startIndex) {
|
|
int size = nums.size();
|
|
// 结束条件
|
|
if (startIndex == size) return;
|
|
|
|
// 初始化一个哈希表用来存储元素是否在数层中使用过
|
|
unordered_map<int, bool> used;
|
|
|
|
for (int i = startIndex; i < size; ++i) {
|
|
// 剪枝，如果元素在数层中使用过则跳过
|
|
if (used.count(nums[i]) == 1) continue;
|
|
// 当当前元素大于等于起始元素之前的元素时，将它添加进去
|
|
if (startIndex == 0 || nums[i] >= nums[startIndex - 1]) {
|
|
subsequences.push_back(nums[i]);
|
|
if (subsequences.size() > 1) result.push_back(subsequences);
|
|
used[nums[i]] = true;
|
|
findSubsequencesDFS(subsequences, result, nums, i + 1);
|
|
subsequences.pop_back();
|
|
}
|
|
}
|
|
}
|
|
|
|
vector<vector<int>> S0491::findSubsequences(vector<int> &nums) {
|
|
vector<int> subsequences{};
|
|
vector<vector<int>> result{};
|
|
findSubsequencesDFS(subsequences, result, nums, 0);
|
|
return result;
|
|
}
|