문자열 순열 알고리즘 JAVA

코딩테스트 진행하다가 순열사용할 때 재활용할 수 있을 것같아서 올려 둔당.

 

문자열에서 각 문자 별로 모든 경우의 수를 구하다가 사용하게 된 순열 알고리즘

중복 제거를 위해 HashSet을 사용했다.

 

String s = "aab" 이면

aab, aba, baa 가 나온다.

import java.util.*;

class Solution {
    // 문자열로 만들 수 있는 모든 경우의 수 (중복x)
    public HashSet<String> allSet;
    
    public void solution(String s) {
        allSet = new HashSet<>();
        permutation("", s);
    }
    
    // 모든 경우의 수를 구하는 순열
    public void permutation(String prefix, String s) {
        int n = s.length();
        if(n==0)
            allSet.add(prefix); // all에 삽입
        else {
            for(int i=0; i<n; i++) {
                permutation(prefix + s.charAt(i),
                                s.substring(0, i) + s.substring(i+1));
            }
        }
    }
}