책에 있는 코드를 썼을 때 결과가 잘 안나와서
reconstruct 부분의 return 부분만 수정했는데
예제는 이상없이 나오는데 왜 오답이 계속 뜨는지 모르겠습니다.

import java.util.*;

public class Main {
static int[][] overlap;//overlap 저장
static ArrayList word;//문자열 저장
static int len;//저장된 문자열 갯수 (포함된 문자열 제외)
static int[][] cache;

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int num=sc.nextInt();
    while(num-->0) {
        int n=sc.nextInt();
        word=new ArrayList<String>();
        sc.nextLine();
        for(int i=0;i<n;i++) {
            String input=sc.nextLine();
            int flag=1;
            for(int j=0;j<word.size();j++) {
                if(word.get(j).contains(input)) {
                    flag=0;
                    break;
                }
            }
            if(flag==1)
                word.add(input);
        }
        len=word.size();
        overlap=new int[len][len];
        overlap();
        cache=new int[len][1<<len];
        for(int i=0;i<len;i++)
            Arrays.fill(cache[i], -1);
        System.out.println(reconstruct(0,0));
    }
    sc.close();
}

public static void overlap() {
    for(int i=0;i<len;i++) {
        for(int j=0;j<len;j++) {
            if(i!=j) {
                overlap[i][j]=0;
                String a=word.get(i);
                String b=word.get(j);
                int len=Math.min(a.length(), b.length());
                for(int k=1;k<=len;k++) {
                    if(a.substring(a.length()-k, a.length()).equals(b.substring(0, k)))
                        overlap[i][j]=k;
                }
            }
        }
    }
}

public static int restore(int last,int used) {
    if(used==(1<<len)-1)
        return 0;

    if(cache[last][used]!=-1)
        return cache[last][used];

    cache[last][used]=0;
    for(int next=0;next<len;next++) {
        if((used&(1<<next))==0) {
            int cand=overlap[last][next]+restore(next,used+(1<<next));
            cache[last][used]=Math.max(cache[last][used], cand);
        }
    }
    return cache[last][used];
}

public static String reconstruct(int last,int used) {
    if(used==(1<<len)-1)
        return "";

    for(int next=0;next<len;next++) {
        if((used&(1<<next))!=0)continue;

        int ifUsed=overlap[last][next]+restore(next,used+(1<<next));

        if(restore(last,used)==ifUsed) {
            //최대값일때
            String ret="";
            if(used==0)
                ret+=word.get(next).substring(0, overlap[last][next]);
            return ret+=(word.get(next).substring(overlap[last][next])+reconstruct(next,used+(1<<next)));
        }
    }
    return "error";
}

}