import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class RESTORE {

private static final Scanner scanner = new Scanner(System.in);

public static boolean check(String f, String e, int s) {
    String sub = e.substring(0, s);
    return f.contains(sub);
}

public static String concat(String f, String e) {
    int size = Integer.min(f.length(), e.length());

    int result = 0;
    for(int i=1; i<=size; i++) {
        if(check(f, e, i)) {
            result = i;
        }
    }

    return f + e.substring(result);
}

public static String solution(List<String> subs, List<Integer> indexes, String[] cache) {
    if(indexes.size() == 1) {
        return subs.get(indexes.get(0));
    }

    int cacheIndex = merge(indexes);
    if(cache[cacheIndex] != null) {
        return cache[cacheIndex];
    }

    int size = indexes.size();
    int minSize = Integer.MAX_VALUE;
    String result = "";
    for(int i=0; i<size; i++) {
        int index = indexes.remove(i);
        String sub = solution(subs, indexes, cache);
        String concated = concat(subs.get(index), sub);
        if(concated.length() < minSize) {
            result = concated;
            minSize = result.length();
        }
        indexes.add(i, index);
    }

    cache[cacheIndex] = result;

    return result;
}

public static int merge(List<Integer> indexes) {
    int result = 0;
    for(int index : indexes) {
        result = result + (1 << index);
    }
    return result;
}

public static void main(String[] args) {
    int C = scanner.nextInt();
    while(C-->0) {
        int k = scanner.nextInt();
        scanner.nextLine();
        List<String> subs = new ArrayList<>(k);
        List<Integer> indexes = new ArrayList<>(k);
        for(int i=0; i<k; i++) {
            subs.add(scanner.nextLine());
            indexes.add(i);
        }

        int size = 1 << k;
        String[] cache = new String[size];


        String result = solution(subs, indexes, cache);
        System.out.println(result);

    }
}

}

구현에서는 길이를 미리 구해놓고 나중에 reconstruct하는데
해당 방법말고 처음부터 캐시에 문자열을 저장하는 방법으로 접근해봤는데
오답이라고 나옵니다.

테스트 케이스는 잘 작동하는데 어디에서 예외인 건지 감을 못잡겠네요
도움 부탁드립니다