与首个字符交换

第一个字符+剩余所有字符。回溯是注意状态的恢复。

    /**
     *输入一个字符串,按字典序打印出该字符串中字符的所有排列。
     * 例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的
     * 所有字符串abc,acb,bac,bca,cab和cba。
     * @param str 字符串
     * @return 排列得到的所有字符串
     */
    public ArrayList<String> Permutation(String str) {
        chars=str.toCharArray();
        Permutation(0);
        permutes.sort(String::compareTo);
        return permutes;
    }
    private ArrayList<String> permutes=new ArrayList<>();
    private char[] chars;
    public void Permutation(int starIndex){
        if(starIndex==chars.length-1){
            permutes.add(String.valueOf(chars));
        }
        Set<Character> set=new HashSet<>();
        for(int i=starIndex;i<chars.length;i++){
            if(set.contains(chars[i])){
                continue;
            }
            set.add(chars[i]);
            //chars[i] 固定在第 starIndex 位
            char temp=chars[i];
            chars[i]=chars[starIndex];
            chars[starIndex]=temp;
            Permutation(starIndex+1);
             temp=chars[i];
            chars[i]=chars[starIndex];
            chars[starIndex]=temp;
        }

    }