백준 - N과 M (1) : 15649번

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

15649번: N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

N=4, M=4가 주어지면, 아래와 같이 12(4*3)개의 경우가 발생한다.

아래 1 4 와 4 1과 같이 순서가 다른 경우는 다른 것으로 판단해야 함.

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

"중복 없이"라는 조건이 있음으로 한번 수열에 포함된 수는 수열을 완성할때까지 다시 포함되면 안됨으로 포함 여부를 판단하기 위해 included라는 배열을 사용한다.

 

n = 4, m = 2를 입력하면, 아래와 같은 순서로 실행된다.

 

"1. go(4,2)" : nm에 1추가 (nm = 1)

"2. go(4,2)" : nm에 2추가 (nm = 1,2)

"3. go(4,2)" : nm.size()가 m임으로 nm의 내용 1,2 출력 후 return

"2. go(4,2)" 로 돌아감. nm에서 2를 pop_bakc하고, for문을 통해 i 증가시킨 후 nm에 3을 추가함.

 

 

 

#include <bits/stdc++.h>

using namespace std;
bool included[10]; //중복 체크
vector <int> nm;
void NM1(int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM1(n, m);
    return 0;
}

void NM1(int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!included[i]) {
            included[i] = true;
            nm.push_back(i);
            NM1(n, m);
            nm.pop_back();
            included[i] = false;
        }
    }
}