C++でのサブシーケンスの増加

整数配列があるとすると、与えられた配列の可能なすべての異なる増加部分列を見つけることがタスクであり、増加部分列の長さは少なくとも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の場合はnumsのサイズで開始します
  • x：=nums [i]
  • 訪問したセットにxがある場合は、ループの次の部分をスキップします
  • 訪問したセットにxを挿入
  • tempが空であるか、temp <=xの最後の要素である場合、
    • xを一時に挿入
    • solution（nums、i + 1、temp）を呼び出す
    • 一時の終わりから1つの要素を削除します
• メインメソッドから、solve（nums、0、temp）を呼び出します
• return 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, ],]