मान लीजिए हमारे पास एक पूर्णांक सरणी है, हमारा कार्य दी गई सरणी के सभी संभावित विभिन्न बढ़ते उपअनुक्रमों को ढूंढना है, और एक बढ़ते उपअनुक्रम की लंबाई कम से कम 2 होनी चाहिए। इसलिए यदि सरणी [4,6,7,7] है, तो आउटपुट इस तरह होगा: [[4,6], [4,7], [4,6,7], [4,6,7,7], [6,7], [6,7,7], [7,7], [4,7,7]]।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- सभी परिणामों को संग्रहीत करने के लिए
resनामक एक सरणी परिभाषित करें solveनामक एक विधि बनाएं। यहnums सरणी, start, और temp सरणीलेगा- यदि
temp का आकार > 1, तोtempकोresमें डालें visitedनामक एक सेट बनाएंi = start से nums का आकारतक:x := nums[i]- यदि
x, visited सेट में है, तो लूप के अगले भाग को छोड़ें xकोvisitedसेट में डालें- यदि
temp खाली है या temp का अंतिम तत्व <= x:xकोtempमें डालेंsolve(nums, i+1, temp)कॉल करेंtempके अंत से एक तत्व हटाएं
- यदि
- मुख्य विधि से,
solve(nums, 0, temp)कॉल करें resलौटाएं
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << "[";
for(int j = 0; j < v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]" << endl;
}
class Solution {
public:
vector<vector<int>> res;
void solve(vector<int>& nums, int start, vector<int> temp){
if(temp.size() > 1){
res.push_back(temp);
}
set<int> visited;
for(int i = start; i < nums.size(); i++){
int x = nums[i];
if(visited.count(x)) continue;
visited.insert(x);
if(temp.empty() || temp[temp.size() - 1] <= x){
temp.push_back(x);
solve(nums, i + 1, temp);
temp.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
res.clear();
vector<int> temp;
solve(nums, 0, temp);
return res;
}
};
int main(){
vector<int> v = {5,6,7,8};
Solution ob;
print_vector(ob.findSubsequences(v));
}
इनपुट
[4,6,7,8]
आउटपुट
[[5, 6, ],[5, 6, 7, ],[5, 6, 7, 8, ],[5, 6, 8, ],[5, 7, ],[5, 7, 8, ],[5, 8, ],[6, 7, ],[6, 7, 8, ],[6, 8, ],[7, 8, ],]