[C++] BOJ 15649 / 백트래킹 (M과 N(1), 백트래킹 첫 도전)

문제 분석

 

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

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제이다.

 

해결 방법

비어있는 리스트에 가능한 숫자를 넣어가며, 리스트의 사이즈가 M이 됐을 때를 base case로 설정하여 구현한다.

중복 없이 고른다는 조건이 있기 때문에, 이미 리스트에 포함되어 있는 숫자인지 체크하기 위한 배열을 선언해야한다.

 

코드

#include <iostream>
using namespace std;

int n,m;
int arr[10];
bool choice[10];

void pick(int k) {
    if(k==m) {
        for(int i=0;i<m;i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i=1;i<=n;i++) {
        if(choice[i]) continue;
        arr[k] = i;
        choice[i] = 1;
        pick(k+1);
        choice[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    pick(0);
    
}