애너그램6443

https://www.acmicpc.net/problem/6443

처음에 dfs로 순열조합을 만들고 hashset 을 사용했으나 메모리 초과가 났다
그래서 hashset 을 제거하였으나 이번에는 출력초과가 났다. 중복이 제거가 안되어서그랬다

결국 한참 고민하다 해결책을 못찾아서 풀이를 검색해보고 풀었다
풀이방식이 생각지도 못한 방식이고 간단하다
입력받은 글자의 알파벳을 카운트해서 배열로 저장한다
알파벳 카운트 배열을 가지고 dfs로 순열 조합을 만들면된다

시간복잡도
N개의 단어가 주어지고 단어당 최대 10만개 이하의 애너그램 조합을 만들 수 있다
N X 10만 인듯하다..

import java.io.*;
import java.util.*;
public class Main {
    static int[] alphacnt;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        sb = new StringBuilder();
        String input;
        alphacnt = new int[26];

        for(int i = 0; i < N; ++i){
            input = br.readLine().toString();

            for (int j = 0; j < input.length(); j++) {
                alphacnt[input.charAt(j)-'a']++;
            }

            dfs(input.length(), sb);

            for (int j = 0; j < 26; j++) {
                alphacnt[j] = 0;
            }
        }

    }

    public static void dfs(int maxlen, StringBuilder sb){

        if(maxlen == sb.length()){
            System.out.println(sb.toString());
            return;
        }

        for (int i = 0; i < 26; i++) {
            if(alphacnt[i] > 0){
                alphacnt[i]--;
                sb.append((char)(i+'a'));
                dfs(maxlen, sb);
                alphacnt[i]++;
                sb.setLength(sb.length()-1);
            }
        }
    }
}