백준 15652 N과 M (4) / C++

문제 : 15652

풀이 point

백트래킹을 통해 구현한다. 중복 허용 불가 + 선택한 수를 또 선택이 가능하다.

풀이 방법

선택한 수를 또 선택하기 위해 visit배열을 없앤다.
중복 허용 불가를 위해 for문의 시작을 그 전 숫자를 선택하지 못하도록 변경한다.

코드

//백준 15652, N과 M(4)

#include <iostream>

int N, M;
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}; i<=N; ++i){
        ans[depth] = i;
        back(depth+1, i);
    }
}

int main (){

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

    return 0;
}