难度 hard
来源：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=117&&tqId=37778&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
描述
输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例1
输入：
"ab"

返回值：
["ab","ba"]

说明：
返回["ba","ab"]也是正确的
示例2
输入：
"aab"

返回值：
["aab","aba","baa"]

示例3
输入：
"abc"

返回值：
["abc","acb","bac","bca","cab","cba"]

解题思路：这道题就是NC42 有重复项数字的所有排列的翻版，只是那道题用的是数组，这里改成字符串，其实相当于是字符数组，代码逻辑基本是一样的，思路可以直接参考NC42 有重复项数字的所有排列。

代码

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        ArrayList<Character> out = new ArrayList<>();
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        boolean[] vis = new boolean[chars.length];
        dfs(res, out, chars, vis);
        return res;
    }

    public void dfs(ArrayList<String> res, ArrayList<Character> out, char[] chars, boolean[] vis){
        if(out.size()==chars.length){
            res.add(chars2String(out));
            return;
        }
        for(int i=0; i<chars.length; i++){
            if(vis[i] || (i>0 && chars[i]==chars[i-1] && !vis[i-1])) continue;
            vis[i] = true;
            out.add(chars[i]);
            dfs(res, out, chars, vis);
            vis[i] = false;
            out.remove(out.size()-1);
        }
    }
    public String chars2String(ArrayList<Character> characters){
        StringBuffer sb = new StringBuffer();
        for (Character c : characters) {
            sb.append(c);
        }
        return sb.toString();
    }
}

相似题目：
46. 全排列
NC42 有重复项数字的所有排列

参考资料：