백준 6603 로또(c++)

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

6603번: 로또

로또의 당첨 번호는 6개입니다. 입력받은 숫자들 중 6개의 순서쌍을 오름차순으로 모든 경우의 수를 출력해 주는 문제입니다. 

백트래킹으로 접근할 수 있습니다.

만약 해당 인덱스의 숫자를 사용한다면 함수는 다음과 같이 정의 할 수 있습니다.

solve(a, index+1, cnt+1)

해당 인덱스의 숫자를 사용하지 않는다면, 개수는 늘려주지 않고, 해당 인덱스만 1 늘려주면 끝입니다.

solve(a, index+1,cnt)

a : 입력받은 임의의 로또 숫자 배열

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> lotto;

void solve(vector<int> &a, int index, int cnt)
{
    if (cnt == 6)
    {
        for (int num : lotto)
        {
            printf("%d ", num);
        }
        printf("\n");
        return;
    }
    int n = a.size();
    if (n == index)
        return; // index == n번째 불가능
    lotto.push_back(a[index]);
    solve(a, index + 1, cnt + 1); // index번째 선택한 경우
    lotto.pop_back();
    solve(a, index + 1, cnt); // index번째 선택하지 않은 경우
}
int main()
{
    while (1)
    {
        int n;
        scanf("%d", &n);
        if (n == 0)
            break;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        solve(a, 0, 0);
        printf("\n");
    }
}