import java.util.*;

class Main {

private static int numOfFriends;
private static int numOfFoods;
private static String[] nameArr;
private static boolean[][] eatableTable;
private static int nowMinCount;

public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);

    int testcaseN = keyboard.nextInt();

    int[] resultArr = new int[testcaseN];

    for (int i = 0; i < testcaseN; i++) {

        numOfFriends = keyboard.nextInt();
        nameArr = new String[numOfFriends + 1];

        numOfFoods = keyboard.nextInt();
        nowMinCount = numOfFoods;
        eatableTable = new boolean[numOfFriends + 1][numOfFoods + 1];

        for (int j = 0; j < numOfFriends; j++) {
            nameArr[j + 1] = keyboard.next();
        }
        for (int j = 0; j < numOfFoods; j++) {
            int eatableNum = keyboard.nextInt();
            for (int k = 0; k < eatableNum; k++) {
                String tmp = keyboard.next();
                for (int l = 0; l < numOfFriends; l++) {
                    if (nameArr[l + 1].equals(tmp))
                        eatableTable[l + 1][j + 1] = true;
                }
            }

        }

        retMinCount(new boolean[numOfFriends + 1],
                new boolean[numOfFoods + 1]);

        System.out.println(nowMinCount);
    }
}

// 친구들이 모두 체크 다됬으면 리턴해줌
// 한개씩 음식을 더 체크해줌 - 체크하는 음식은 현재 체크안된 친구에 대한 것
private static void retMinCount(boolean[] checkedFriend,
        boolean[] checkedFood) {

    // 안먹은 친구들이 있는 지 확인
    if (trueCount(checkedFriend) == numOfFriends) {// 안먹은 친구들이 한명도 없으면
        nowMinCount = trueCount(checkedFood);// 현재 체크된 음식 수를 계산 및 리턴 후
        return; // 종료
    }

    else {// 안먹은 친구들이 한명이라도 있으면 - 안먹은 친구들이 필요한 음식을 하나 더 체크해주고 다시 호출
        boolean[] checkingFoodArr = checkedFood.clone();

        while (true) {// 음식이 모두 체크될 때 까지
            int bestIndex = findAndEatBest(checkedFriend, checkingFoodArr);

            if (bestIndex < 1 || bestIndex > numOfFoods)// 베스트 인덱스가없으면
                                                            // 다끝난것
                break;
            else {// 해당인덱스를 먹은 것 처리해주고 재호출
                boolean[] cFriend = checkedFriend.clone();
                boolean[] cFood = checkedFood.clone();

                cFood[bestIndex] = true;
                checkingFoodArr[bestIndex] = true;

                if (trueCount(cFood) >= nowMinCount)//체크 후의 음식 배열이현재 최소값보다 더 커지면 호출을 안함.
                    continue;


                for (int j = 0; j < numOfFriends; j++) {// 해당 음식을 먹은 친구들을 먹음
                                                        // 표시 처리해줌
                    if (eatableTable[j + 1][bestIndex] == true) {
                        cFriend[j + 1] = true;
                    }
                }

                retMinCount(cFriend, cFood);
            }
        }
    }
}

// boolean배열 내부의 true갯수 반환
private static int trueCount(boolean[] arr) {
    int count = 0;
    for (int i = 0; i < arr.length; i++)
        if (arr[i] == true)
            count++;
    return count;
}

// 현재 상황중에 가장 효율이 높은 것을 먹게하는 함수
// 효율이 높다는것은 안먹은음식들 중에서 현재 안먹은 친구들이 가장 많이 해당되는 음식을 말함
//없을 경우 0리턴
private static int findAndEatBest(boolean[] checkedFriend,
        boolean[] checkedFood) {
    // 가장 중복횟수가 많은 것을 찾음

    int maxCount = 0;
    int maxIndex = 0;
    for (int i = 0; i < numOfFoods; i++) {
        if (checkedFood[i + 1] == false) {// 안먹은음식에대해
            int thisMaxCount = 0;
            for (int j = 0; j < numOfFriends; j++) {// 안먹은친구가 몇명원하는지 찾음
                if (eatableTable[j + 1][i + 1] == true)
                    thisMaxCount++;
            }
            if (maxCount < thisMaxCount)// 최대카운트가 더 크면 인덱스 갱신
            {
                maxIndex = i + 1;
                maxCount = thisMaxCount;
            }
        }

    }
    return maxIndex;
}

}

현재 저의 코드입니다.
처음에 분할탐색법으로 현재 최적화값을 유지해 주면서 최적화값이상에 대해서는 재귀함수를 호출하지 않도록 하여 가지치기를 하였구요.
시간초과가 뜨길래 추가로 호출하는순서를 findAndEatBest라는 함수를 만들어서 최대한 많이 중복되는 값부터 호출하도록 햇는데도 계속 시간초과가 뜨네요. 어떤방식으로 더 개선할 수 있을까요?