题解 | #字符串的排列#TOP58

思路:
两种方法 1.起始位置有n种选择，所以每次更换i位置和起始位置的值，然后再递归
2.起始位置固定，例如第1个数，固定，剩下的有 n - 1 种可能，然后递归，回溯

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       if(str == null){
           return null;
       }
        ArrayList<String> result = new ArrayList<>();
        permutationHelper(str.toCharArray(),0,result);
        Collections.sort(result);
        return result;
    }
        public void permutationHelper(char[] chars, int start, ArrayList<String> result){
        if(start==chars.length -1 ){
            result.add(String.valueOf(chars));
            return;
        }
        Set<Character> charSet = new HashSet<>();
        for (int i = start;i<chars.length;i++){

            if(!charSet.contains(chars[i])) {
                charSet.add(chars[i]);
                char temp = chars[i];
                chars[i] = chars[start];
                chars[start] = temp;
                //i + 1后的全排列
                permutationHelper(chars, start + 1, result);
                char temp2 = chars[i];
                chars[i] = chars[start];
                chars[start] = temp2;
            }
        }
    }
}