ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে, আমাদের কাজ হল দেওয়া অ্যারেতে সব সম্ভাব্য ভিন্ন ক্রমবর্ধমান সাবসিকোয়েন্স বের করা, এবং একটি ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য কমপক্ষে ২ হওয়া উচিত। তাই যদি অ্যারেটি হয় [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; } }; 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, ],]
