백준 15651번: N과 M (3)

문제

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

풀이

재귀를 이용한 backtraking으로 문제를 풀었다. 중복을 허용하기 위해서 m 만큼 같은 곳을 방문할 수 있도록 해주었다.

#include<iostream>
using namespace std;

int n, m;
int num[8]={};
int visit[8]={};

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

int main(){
    cin>>n>>m;
    backtracking(0);
}