6603)로또

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

k개의 수가 있는 집합 S에서 6개의 수들로 만들 수 있는 조합을 모두 출력해야 한다.

DFS를 변형해 문제를 푼다는 사실은 알았지만 어떻게 변형해야 할 지 몰라서

결국 다른 사람의 코드를 봤다.

DFS에 시작값을 주고 시작값부터 k까지 i값을 증가시키며

DFS가 재귀 호출할 때 i+1을 넘겨주면 재귀 호출의 깊이가 깊어질 때 한 층 낮았던 i값을 다시 볼 필요가 없다.

예를들어 0~3까지 수열을 깊이가 3일 때까지 DFS를 수행할 때 DFS의 콜트리에서 i값은 아래 그림과 같다.

#include<iostream>
#define LOTTO_NUM 6
using namespace std;
 
int lotto[13], combi[13];
int k;
 
void dfs(int start, int depth = 0) {
    if (depth == LOTTO_NUM) {
        for (int i = 0; i < LOTTO_NUM;i++) {
            cout << combi[i] << " ";
        }
        cout << endl;
    }
    
    for (int i = start; i < k; i++) {
        combi[depth] = lotto[i];
        dfs(i+1, depth+1);
    }
}
 
int main() {
    while (cin >> k && k) {
        for (int i = 0; i < k;i++) cin >> lotto[i];
        dfs(0);
        cout << endl;
    }
 
    return 0;
}