[ C++ ] #15650 N과 M(2) ( 실버 III )

문제

---

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다

풀이

---

백트래킹에 대한 감이 아직 없는건지 N과M(1)과 비슷한 문제인데 꽤 헤맸다.

하지만 그저 간단하게 for문을 이전 n 값부터 돌리면 되는 거였다.

num[n-1]을 위해 num은 index 1부터 사용했다.

몇개 더 풀어봐야할 것 같다.

#include <iostream>

using namespace std;

int N, M;
int num[10];
int check[10];

void NM(int n){

    if(n==M+1){
        for(int i=1;i<M+1;i++) {
            cout << num[i] << " ";
        }
        cout<<"\\n";
        return;
    }

    for(int i=num[n-1];i<N+1;i++){

        if(check[i]==0) {
            num[n] = i;
            check[i] = 1;
            NM(n + 1);
            check[i] = 0;

        }

    }

    return;

}

int main(){

    cin>>N>>M;

    num[0]=1;
    NM(1);

}