Java打印任意字符串的全排列，全网最优解

最近遇到一道题：打印任意字符串的全排列，如输入"ABC"，打印ABC CBA ACB CAB BAC BCA

像这种工作中不常用的算法竟然一时没有想出来，作为知名大厂的高级工程师，我的内心告诉我，必须将它解决，

大概找了一下网上的解决方案，没有找到我认为的最优解，所以分享出我的解决方案。

全排列的原理是将每一个元素，与其他剩下的所有元素分别组合一次。

编程建模思想：将每一个元素，与其他剩下的所有元素分别组合一次，如果剩下的元素数大于2，则使用递归拆分第一个和剩下的，直到只剩下2个元素，交换两个元素的位置并拼接打印，结束递归。

如果我的文字描述还是没有讲清楚，仔细观察一下代码中的全排列注释中的全排列结果集，就能看出全排列的规律，而程序就是这个规律的实现。

import java.util.ArrayList;
import java.util.List;

public class FullPermutation {

    public static void fullPermutation(String str) {
        char[] chars = str.toCharArray();
        List<Character> characterList = new ArrayList<>();
        for (char c : chars) {
            characterList.add(c);
        }
        recursivePermutation("", characterList);
    }

    /**
     * algorithm: every element should combine with all other left elements,
     * if other elements length larger than 2 then recursive split first and left 
     * until left only two elements, then exchange this two elements.
     *
     * <p>
     * 1234 1243
     * 1324 1342
     * 1423 1432
     * <p>
     * 2134 2143
     * 2314 2341
     * 2413 2431
     * <p>
     * 3124 3142
     * 3214 3241
     * 3412 3421
     * <p>
     * 4123 4132
     * 4213 4231
     * 4312 4321
     */

    // arranged must be String, can not use StringBuilder
    private static void recursivePermutation(String arranged, List<Character> leftElements) {
        if (leftElements.size() > 2) {
            for (int i = 0; i < leftElements.size(); i++) {
                Character element = leftElements.get(i);
                List<Character> newLeftElements = new ArrayList<>(leftElements);
                newLeftElements.remove(i);
                //recursive split and combine
                recursivePermutation(arranged + element, newLeftElements);
            }
        } else if (leftElements.size() == 2) {
            //exchange the last two elements
            //print arranged + elements.get(0) + elements.get(1)
            System.out.print(arranged);
            System.out.print(leftElements.get(0));
            System.out.print(leftElements.get(1));
            System.out.print("\n");
            //print arranged + elements.get(1) + elements.get(0)
            System.out.print(arranged);
            System.out.print(leftElements.get(1));
            System.out.print(leftElements.get(0));
            System.out.print("\n");
        }
    }


    public static void main(String[] args) {
        fullPermutation("ABCD");
    }
}