[[problem:ALLERGY]] 같은 유형의 문제를 보면 기본적으로 음식을 선택하는 조합을 찾게 되는데 아래와 같은 재귀함수를 자주 구축하고 있습니다. for문을 봐주세요~

void allergy3(int cur, long long selected, int minFood)
{
    if (best <= minFood) return;

    if (selected == (1 << n) - 1)
    {
        best = min(best, minFood);
        return;
    }
    for (int next = cur + 1; next < m; ++next)
        allergy3(next, selected | foodlist[next], minFood+1);
}

allergy3(-1, 0, 0)의 형태로 함수를 동작시켜서

0, 1, 2, ...., m-1의 원소들을 선택하는 모든 조합을 탐색합니다.

그런데 문제를 조금 달리 생각해보면 각각의 원소를 선택하거나 안하는 상황으로 나눌 수 있습니다. 즉 2^m개의 경우의 수를 가진 탐색으로도 바라볼 수 있다는 것이죠. 따라서 아래와 같은 코드도 가능합니다.

void allergy4(int cur, long long selected, int minFood)
{
    //cur 범위 벗어난 경우
    if (cur == m) return;

    if (best <= minFood) return;

    if (selected == (1 << n) - 1)
    {
        best = min(best, minFood);
        return;
    }

    //선택 안함
    allergy4(cur + 1, selected, minFood);
    //선택함
    allergy4(cur + 1, selected | foodlist[cur], minFood + 1);
}

결과적으로 allergy3의 경우에는 mC1 + mC2 + mC3 + ... + mCm 가지 경우를 도출하고
allergy4의 경우에는 2^m가지 경우를 도출합니다. 따라서 탐색하는 조합의 수는 동일합니다. (mC0을 제외하고...)

제가 궁금한 점은 이 두 함수가 똑같은 답을 도출하느냐는 것입니다.

일단 약간의 차이점은 allergy3의 경우 적어도 한개 이상의 원소를 선택한다는 점이 있는 것 같습니다.

정리하자면 조합의 경우엔 탐색 순서를 고정시켜서
for(int next = cur+1; ...)라는 반복문을 이용하여 코드를 짜고 있습니다. 이 코딩 방식과 선택하는경우, 선택하지 않는 경우로 나누는 코딩방식의 논리적, 결과적 차이점이 있는지 매우 궁금합니다. ^{^}