[BOJ/15655번N과M(6)] c++ / backtracking

문제

주어진 N개의 원소로 이루어진 배열에서 M개의 원소를 골라 수열을 출력하는 문제

-중복되어선 안됨

-수열은 사전순으로 증가하는 순서로 출력되어야 함

 

생각

백트래킹 사용해서 풀어야겠다 생각함

 

문제풀이

1.배열을 정렬해줌

2.func(0, 0) - cnt, cur

3.만약 cnt의 개수가 M이면, 수열 출력

4.cur 부터 N까지 사용하지 않은 arr[i]이 나오면

4-1.사용표시 + res[cnt] 에 arr[i] 저장

4-2.func(cnt+1, i) 호출

4-3.사용표시 삭제

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int arr[10], res[10];
int isused[10];
void func(int cnt, int cur) {
  if ( cnt == M ) {
    for ( int i = 0; i < M; i++ ) 
      cout << res[i] << ' ';
    cout << '\n';
    return;
  }

  for ( int i = cur; i < N; i++ ) {
    if ( !isused[i] ) {
      isused[i] = 1;
      res[cnt] = arr[i];
      func(cnt+1, i);
      isused[i] = 0;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M;
  for ( int i = 0; i < N; i++ ) cin >> arr[i];
  sort(arr, arr+N);

  func(0, 0);
}