백준 6603 로또

<링크>

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

<소스코드>

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> num(13);
vector<int> v;
int N;
void dfs(int, int);
int main()
{
    while (1)
    {
        scanf("%d", &N);
        if (N == 0)
            break;
        for (int i = 1; i <= N; ++i)
            scanf("%d", &num[i]);
        dfs(1, 0);
        printf("\n");
    }
}
void dfs(int i, int len)
{
    if (len == 6) {
        for (int i = 0; i < 6; ++i)
            printf("%d ", v[i]);
        printf("\n");
        return;
    }
    if (i > N)
        return;
    v.push_back(num[i]);
    dfs(i+1, len + 1);
    v.pop_back();
    dfs(i+1, len);
}

<풀이>

조합을 만들 때는

num[i]를 조합에 넣는다, 안넣는다로 따진다.

순열처럼 for문을 쓰지 않고 재귀를 돌려도 된다.

void dfs(int i, int len)
{
    if (len <= ?) {
        ;
    }
    if (i > N)
        return;
    v.push_back(num[i]);
    dfs(i+1, len + 1);
    v.pop_back();
    dfs(i+1, len);
}

이렇게 하면 len의 조건을 수정해서 좀 더 유연하게 쓸 수 있다.

로또같은 경우는 len==6일때 출력하는 방식이었다.

위코드에서 기저점을 len<=3 으로 바꾸면,

길이가 3 이하인 조합을 중복없이 알아낼 수 있다.

예를들어

<N=6, num={1,2,3,4,5,6}>
len=3이하일때 만들수있는 조합
1
1 2
1 2 3
1 2 4
1 2 5
1 2 6

1 3
1 3 4
1 3 5
1 3 6

1 4
1 4 5
1 4 6

1 5
1 5 6

1 6

2
2 3
2 3 4
...

위와같은 조합들로 처리하고싶을 때 편리하다.

관련문제 : 백준 15686 치킨배달

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

넣는다, 안넣는다 방식으로 재귀호출하면

i가 한도끝도없이 이어지게되므로 i가 N을 초과하면 리턴해줘야한다.