HackMD
491.Non-decreasing Subsequences
tags: Medium,Array,Hash Table,Backtracking,Bit Manipulation
491. Non-decreasing Subsequences
題目描述
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]]
Example 2:
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
Constraints:
- 1 <=
nums.length<= 15 - -100 <=
nums[i]<= 100
解答
C++
class Solution {
public:
void dfs(vector<int>& nums, set<vector<int>>& ans, vector<int>& path, int i = 0) {
if (i >= nums.size()) {
if (path.size() >= 2) ans.insert(path);
return;
}
if (path.size() == 0 || nums[i] >= path.back()) {
path.push_back(nums[i]);
dfs(nums, ans, path, i+1);
path.pop_back();
}
dfs(nums, ans, path, i+1);
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> ans;
vector<int> path;
dfs(nums, ans, path);
return vector(ans.begin(), ans.end());
}
};
Backtracking走一遍就好
Yen-Chi ChenFri, Jan 20, 2023
Python
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
ans = set()
def BT(path = [], i = 0):
if i >= len(nums):
if len(path) >= 2: ans.add(tuple(path))
return
if not path or nums[i] >= path[-1]:
BT(path + [nums[i]], i+1)
BT(path, i+1)
BT()
return ans
Yen-Chi ChenFri, Jan 20, 2023
