回溯：回溯字符串

题目https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=295&tqId=23291&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
第一题目是要求，给一个字符串，然后排列出他们不同的排序方法。这个题目一看到就是想到回溯，但是奈何功力不够，还是求助了题解。首先定一个全局的res列表，然后if判断输入的字符串是否为空，接下来就是把字符串str转换成char数组，转换完成后排序一下。定一个StringBuilder，方便存储字符顺序。然后定一个map，存储已经访问的下标（这里感觉用Boolean数组更好点）。接下来就是开始回溯。回溯方法第一个肯定是需要if条件判断回溯结束，如果StringBuilder字符串track的长度等于char数组的长度，就可以继续判断res中是否存在这一个字符串，如果没有存在就加入到res中，如果存在直接return返回上一层。
循环中需要先判断map标记，如果map存在i这一个key说明已经遍历过，可以直接跳过下一个，反之，track把当前下标的这个字符append到字符串中，然后map标记当前元素已经遍历过，继续回溯。
回溯结束过后，track需要删除掉最后一个元素，map同理。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if(str == null || str.length() == 0) return result;
        char[] charStr = str.toCharArray();
        // 使用treeSet来保证结果是按照字典序排列的，不用事先排列
        TreeSet<String> resSet = new TreeSet<String>();
        Permutation(charStr,0,resSet);
        result.addAll(resSet);
        return result;
    }

    public void Permutation(char[] chars,int begin,TreeSet<String> treeSet){
        if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1) { return ; }
        if(begin == chars.length-1){
            // 使用交换，可以节省原来使用的memo记录数据的空间
            treeSet.add(String.valueOf(chars));
        }else{
            for(int i=begin;i<chars.length;i++){
                swap(chars,begin,i);
                // 设定下标从上一次的下一个下标开始，可以减少循环次数
                Permutation(chars,begin+1,treeSet);
                swap(chars,begin,i);
            }
        }
    }

    public void swap(char[] chars,int begin,int i){
        char temp = chars[begin];
        chars[begin] = chars[i];
        chars[i] = temp;
    }
}