[백준][c++] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649

 

문제 해석

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 사전순으로 출력

알고리즘 분류

• 백 트래킹

풀이

• 재귀함수와 불리언 배열을 이용해서 해결한다
• endl 을 사용하면 시간초과가 발생하니 주의

코드

#include <iostream>

using namespace std;


static int N,M;
static int arr[8];
static bool check[8];

void find(int len) {
    if (len == M) {
        for (int i=0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for(int i = 1; i <= N; i++) {
        if (check[i]) continue;
        check[i] = true;
        arr[len] = i;
        find(len + 1);
        check[i] = false;
    }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
    cin >> N >> M;
    find(0);
    return 0;
}