一、概念
现有一个字符串，要打印出该字符串中字符的全排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
可以基于回溯法来解决这个问题。

二、代码

public class Permutation {
    //输出字符串str的全排列组合
    public void dump(String str) {
        List<String> list = getPermutation(str);
        for(String s:list) {
            System.out.println(s);
        }
    }
    //返回字符串str的全排列组合
    public List<String> getPermutation(String str) {
        List<String> resultList = new ArrayList<>();
        //若字符串长度为0，则返回空列表
        if(null==str|| str.isEmpty()){
            return (List<String>)resultList;
        }else {
            //递归的初始值为（str数组，空的结果list，初始下标0）
            backtrace(str.toCharArray(),resultList,0);
            Collections.sort(resultList);
            return (List<String>)resultList;

        }
    }

    /**
     * 回溯算法
     * @param array 字符数组
     * @param list  结果列表
     * @param index 执行交换的索引
     */
    private void backtrace(char[] array,List<String> list,int index){
        //若索引已到最后，则做好收集存储，并返回
        if(index == array.length-1){
            if(!list.contains(new String(array))){
                list.add(new String(array));
                return;
            }
        }
        //若索引未到最后一个位置，则继续执行
        else{
            for(int j=index;j<array.length;j++){
                //交换索引index和j的元素
                swap(array,index,j);
                //继续回溯算法
                backtrace(array,list,index+1);
                //再复原回去
                swap(array,index,j);
            }
        }
    }
    //交换array字符数组中索引为i和j位置的元素
    private void swap(char[] array, int i, int j) {
        if (i != j) {
            char t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
    }
}

---

致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。