描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

示例：

• 输入：字符串ABC
• 输出：ABC, ACB, BAC, BCA, CBA, CAB。

思路1：回溯+记录

回溯法+使用boolean数组记录选择过的字符

字符相同时存在重复序列，例如AAB，需要去重

这里通过判断res中是否存在字符串排列去重，也可以使用HashSet去重。

public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        //记录是否已经访问过
        boolean[] visited = new boolean[str.length()];
        StringBuilder track = new StringBuilder();
        recursion(str, track, visited);
        return res;
    }
    public void recursion(String str, StringBuilder track, boolean[] visited){
        if(str.length() == track.length()){
            if(!res.contains(track.toString())) {
                //去重
                res.add(track.toString());
            }
            return;
        }
        for(int i = 0; i < str.length(); i++) {
            if(visited[i]) {
                //跳过已经添加过的字符
                continue;
            }
            track.append(str.charAt(i));
            visited[i] = true;
            //向下搜索
            recursion(str, track, visited);
            //回溯，撤销选择
            track.deleteCharAt(track.length() - 1);
            visited[i] = false;
        }
    }
}

思路2：回溯+交换

1. 第一次循环，A和A交换，begin==0，使用begin+1向下搜索，相当于固定第一位为A
2. 向下搜索，B和B交换，begin==1，使用begin+1向下搜索，相当于固定第二位为B
3. 继续向下搜索，begin==2，最后一位C不需要固定，直接加入序列
4. 第二次循环，A和B交换，begin==0，使用begin+1向下搜索，相当于固定第一位为B
5. ...

class Solution {
    ArrayList<String> res = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        char[] charStr = str.toCharArray();
        recursion(charStr, 0);
        return res;
    }
 
    public void recursion(char[] chars, int begin){
        if(begin == chars.length - 1) {
            String str = String.valueOf(chars);
            if(!res.contains(str)) {
                res.add(str);   
            }
            return;
        }
        for(int i = begin; i < chars.length; i++){
            swap(chars, begin, i);
            recursion(chars, begin + 1);
            swap(chars, begin, i);
        }
    }
 
    public void swap(char[] chars, int begin, int i){
        char temp = chars[begin];
        chars[begin] = chars[i];
        chars[i] = temp;
    }
}