👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

✍️ 아이디어

못풀었다...재귀 자체가 생각이 안남

✍️소스코드

#include <iostream>
using namespace std;
bool c[10]; // 이미 방문한 숫자인지 체크함(백트래킹)
int a[10]; // 숫자 저장용
void dfs(int index, int n, int m)// 로직 자체가 dfs임
{
    if (index == m) // 저장이 다 이루어지면 출력해야지
    {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=1; i<=n; i++) 
    {
        if (c[i]) continue; // 한번 방문한 숫자면 건너뜀(중복 방지)
        c[i] = true; // 숫자에 방문 했다는것을 저장
        a[index] = i; //index 번째에 수를 저장
        go(index+1, n, m); // index에 1 더함(다음 자리에 숫자 저장)
        c[i] = false; // 4,3,2,1 순으로 false로 바뀜 => 3 false 되면 1243 출력
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    dfs(0,n,m);
    return 0;
}

체감난이도	걸린시간	참고	사용 문법
??	1hour	강의 및 블로그	DFS, 재귀, 백트래킹