안녕하세요

ALLERGY문제를 풀던 중에 질문이 있습니다.

먼저 코드는 다음과 같구요

#include <stdio.h>
#include <string.h>

void read();
int getFriendIndex(char* name);
void find(int friendIndex, long long staus, int select);

int tcNum, friendsNum, foodNum;
long long foods[50];
long long friends[50];
char names[50][11];
long long full;
int minNum = 987654321;
int isOut;

int main(){
    scanf("%d", &tcNum);

    for (int tc = 0; tc<tcNum; tc++){
        minNum = 987654321;

        memset(foods, 0, sizeof(long long)* 50);
        memset(friends, 0, sizeof(long long)* 50);

        read();
        isOut = 0;

        find(0, 0, 0);

        if (isOut){
            return -1;
        }

        printf("%d\n", minNum);
    }

    return 0;
}

void read(){
    int eatableNum;
    int friendIndex;
    char name[10];

    scanf("%d %d", &friendsNum, &foodNum);

    full = (1LL << friendsNum) - 1;

    for (int i = 0; i<friendsNum; i++){
        scanf("%s", names[i]);
    }

    for (int food = 0; food<foodNum; food++){
        scanf("%d", &eatableNum);

        for (int eatable = 0; eatable<eatableNum; eatable++){
            scanf("%s", name);
            friendIndex = getFriendIndex(name);

            foods[food] = (foods[food] | (1LL << friendIndex));
            friends[friendIndex] = (friends[friendIndex] | (1LL << food));
        }
    }
}

int getFriendIndex(char* name){
    for (int i = 0; i<friendsNum; i++){
        if (strcmp(names[i], name) == 0){
            return i;
        }
    }

    return -1;
}

void find(int friendIndex, long long status, int select){
    if (status == full){
        if (minNum > select){
            minNum = select;
        }
        return;
    }

    if (friendIndex == friendsNum){
        isOut = 1;
        return;
    }

    if (status & (1LL << friendIndex)){
        find(friendIndex + 1, status, select);
        return;
    }

    for (int i = 0; i<foodNum; i++){
        if (friends[friendIndex] & (1LL << i)){
            find(friendIndex + 1, status | foods[i], select + 1);
        }
    }
}

이렇게 실행하면 시간이 아슬아슬하게 (4초정도)로 통과가 되는데

if (friendIndex == friendsNum){
isOut = 1;
return;
}

이 부분을 제거하고 올리면 시간초과가 뜹니다.
책에서 나온 논리도 그렇고 코드에서도 모든 친구들을 한번씩 살펴봤는데도 못 먹는 친구가 있을 수가 없는데
(게다가 if문이 없으면 더 빨라야 할 것 같은데)
오히려 시간초과가 나서 이상하네요.. 혹시 도움 주실 수 있으신분 계신가요??