1. 題目

給定一個整數(shù)數(shù)組，找到所有不同的可能的升序子序列，一個升序子序列的長度至少應(yīng)為2。

例1: 輸入: [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: 輸入: [65,21,-44,31,-8] 輸出: [[-44,-8],[-44,31],[21,31]]注意事項(xiàng) - 給定數(shù)組的長度不會超過15。 - 給定數(shù)組的范圍為[-100, 100]。 - 給定數(shù)組可能包含重復(fù)，兩個相同的整數(shù)也被算作是升序子序列的特殊情況。

2. 解題

class Solution {set<vector<int>> s;vector<int> v; public:vector<vector<int>> findSubsequences(vector<int> &nums) {dfs(nums,0);return vector<vector<int>>(s.begin(),s.end());}void dfs(vector<int>& nums, int idx){if(idx >= nums.size()){if(v.size() >= 2)s.insert(v);return;}for(int i = idx; i < nums.size(); ++i){dfs(nums,i+1);//不放某數(shù)，找下一個if(v.empty() || v.back() <= nums[i]){ //為空 或者 是升序，放入當(dāng)前數(shù)v.push_back(nums[i]);dfs(nums,i+1);v.pop_back();}}} };

100% 數(shù)據(jù)通過測試
總耗時 209 ms
您的提交打敗了 7.89% 的提交!

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LintCode 1210. 升序子序列（DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。