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 배열, 시작 및 임시 배열을 사용합니다.
• temp의 크기가> 1이면 res에 temp를 삽입합니다.
• 방문이라는 세트 만들기
• 숫자 크기부터 시작하는 범위에 있는 i의 경우
  • x :=숫자[i]
  • 방문 세트에 x가 있으면 루프의 다음 부분을 건너뜁니다.
  • 방문 세트에 x 삽입
  • temp가 비어 있거나 temp <=x의 마지막 요소인 경우
    • 온도에 x 삽입
    • 해결(nums, i + 1, temp) 호출
    • temp의 끝에서 하나의 요소 삭제
• 메인 메소드에서 solve(nums, 0, temp) 호출
• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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, ],]