✅ 조합 ✅ 재귀

문제

1. 해결 로직

수열, 조합 문제로 재귀를 사용하는 문제이다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int lotto[14];
int ans[6];
int num;

void DFS(int start, int depth){
    if(depth == 6){
        for(int i=0;i<6;i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
        return;
    }

    for(int i=start;i<num;i++){
        ans[depth] = lotto[i];
        DFS(i+1, depth+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(1){
        cin >> num;
        if(num == 0) break;

        for(int i=0;i<num;i++){
            cin >> lotto[i];
        }

        DFS(0,0);
        cout << "\n";
    }

    return 0;
}

3. 시간 복잡도

$O(N^2)$

4. Review

이런 재귀함수를 활용한 수열, 조합 문제가 익숙하지 않은데 관련 문제인 N과M 문제 시리즈를 풀어보면 좋을 것 같다.
https://www.acmicpc.net/workbook/view/2052

5. Reference

https://sanghyu.tistory.com/58