아이디어
중복되는 수열을 여러 번 출력하면 안되며... -> visited로 방문 처리
사전 순으로 증가하는 순서 -> 1부터 차례대로 삽입
문제해결
제일 까다로웠던 것은 방문 처리였다.
if (!visited[i]){
visited[i] = true;
arr[cnt] = i;
dfs(cnt + 1);
visited[i] = false;
}
visited방문 처리를 dfs의 뒤에 false로 바꿔줌으로서 첫번째 자리의 수가 바뀔 때마다 방문 상태를 초기화 된 상태로 사용할 수 있게 해주었다
#include <iostream>
#define MAX 9
using namespace std;
int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
void dfs(int cnt){
if (cnt == m){
for (int i = 0; i < m; i++)
cout << arr[i] << " ";
cout << "\n";
return;
}
for (int i = 1; i <= n; i++){
if (!visited[i]){
visited[i] = true;
arr[cnt] = i;
dfs(cnt + 1);
visited[i] = false;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cout.tie(NULL);
cin >> n >> m;
dfs(0);
}
