그냥 "dfs로 풀었다"라고 하시면 dfs로 이 문제를 접근하는 방법이 너무나도 다양하고 디테일에 따른 시간 복잡도가 전부 다르기 때문에 정확한 답변을 드릴 수가 없습니다. 코드를 제시해주셔야 합니다. 더군다나 말씀하신 대로 4^20에 동작하는 코드라면 당연히 통과될 리가 없는데도 통과됐다는 건 그렇지 않은 코드를 작성하셨다는 이야기인데 그게 무엇인지 다른 사람들이 예측할 수는 없습니다.

맞으신 코드를 직접 열어보기로는 그 코드는 4^20이 아니라 20개의 수를 4개의 지정된 그룹에 분배하는 경우의 수인데, 이를 명확하게 표현하는 방법은 저도 모르겠으나 4^20보다는 확실히 작습니다. 왜냐하면 4^20이 되려면 dfs 함수가 호출될 때마다 4개씩의 선택지가 있어야 하는데, 이 코드는 어떤 경우에는 3개 중 하나를 선택해야 할 수도 있고, 2개나 1개일 때도 있기 때문입니다. dfs(cnt) = 4 * dfs(cnt+1)이면 4^20이 나오겠으나, dfs(cnt,i) = i*dfs(cnt+1,i) + (i-1)*dfs(cnt+1,i-1) + (i-2)*dfs(cnt+1,i-2) ... + dfs(cnt+1,1)이기 때문에 훨씬 더 작습니다. 실제 함수 호출 횟수를 계산해보니 10626회밖에 되지 않습니다.