백준 15650번: N과 M (2)

문제

문제 바로가기> 백준 15650번: N과 M (2)

풀이

재귀를 이용한 backtraking으로 문제를 풀었다. 중복 없이 순차적으로 출력하기 위해 반복문의 시작 값을 다음 값으로 설정해주었다.

#include<iostream>
using namespace std;

int n, m;
int num[9]={};
bool visit[9]={false};

void backtracking(int from, int cnt){
    if(cnt == m){
        for(int i=0; i<m; i++) cout << num[i] << ' ';
        cout<<'\n';
        return;
    }
    for(int i=from; i<=n; i++){
        if(!visit[i]){
            visit[i] = true;
            num[cnt] = i;
            backtracking(i+1, cnt+1);
            visit[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    backtracking(1, 0);
}