백준 15650 N과 M(2) / C++

문제 : 15650

풀이 point

중복이 없어야하는 조건으로
1 2 <-> 2 1은 중복처리를 한다.

ex) 4 2의 경우
1 2
1 3
1 4
2 3
2 4
3 4

이 패턴을 보았을 때 맨 앞에 선택된 값보다 작은 값은 뒤에 값으로 오지 못한다는 것을 알 수 있다. 뒤에 오는 값을 앞에 값보다 작지 않도록 통제 하면 된다.
이 값들은 for문과 visit을 통해 선택된다.

풀이 방법

for문과 visit 둘 중 무엇을 통제하는지에 달렸는데 visit은 이미 선택된 값을 다시 선택하지 못하도록 하고 있으므로 for문을 통제하는 것이 맞다.

for문의 시작값을 통제함으로써 1이 선택됐을 때는 2,3,4가 온다.
2가 선택됐을 때는 3, 4
3이 선택됐을 떄는 4만 오도록 만들기 위해 또 다른 인자를 도입한다.

코드

//백준 15650, N과 M(2)
#include <iostream>

int N, M;
int visit[10];
int ans[10];

void back(int depth, int start){
    if(depth == M){
        for(int i{0}; i<M; ++i) std::cout << ans[i] << ' ';
        std::cout << '\n';
        return;
    }
    for(int i{start+1}; i<=N; ++i){
        if(visit[i]) continue;
        visit[i] = true;
        ans[depth] = i;
        back(depth+1, i);
        visit[i] = false;
    }
}

int main(){

    std::cin >> N >> M;
    
    back(0, 0);

    return 0;
}