C++의 조합

두 개의 정수 n과 k가 있다고 가정합니다. 1 ... n 중에서 k개의 가능한 모든 조합을 찾아야 합니다. 따라서 n =4이고 k =2이면 조합은 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]가 됩니다. ]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 이를 해결하기 위해 재귀 함수를 사용할 것입니다. solve() 함수는 n, k, 임시 배열 및 시작을 취합니다. 시작은 처음에 1입니다. 이것은 다음과 같이 작동합니다.
• temp 배열의 크기 =k이면 res 배열에 temp를 삽입하고 반환
• i:=n부터 시작,
  • temp에 i 삽입
  • 해결(n, k, 온도, i + 1)
  • temp의 끝에서 하나의 요소 제거
• solve(n, k, [])와 같은 solve 함수 호출
• 반환 결과

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > 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(int n, int k, vector <int> temp, int start = 1){
      if(temp.size() == k){
         res.push_back(temp);
         return;
      }
      for(int i = start; i <= n; i++){
         temp.push_back(i);
         solve(n, k, temp, i + 1);
         temp.pop_back();
      }
   }
   vector<vector<int> > combine(int n, int k) {
      res.clear();
      vector <int> temp;
      solve(n ,k, temp);
      return res;
   }
};
main(){
   Solution ob;
   print_vector(ob.combine(5,3));
}

입력

5
3

출력

[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]