問題：輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a，b，c所能排列出來的所有字符串a(chǎn)bc，acb，bac，bca，cab和cba。
? ? ? 正常人的思維是，固定第一個字符，然后依次將后面的字符串與前面的交換，那么排列的個數(shù)就是除了第一個字符以外，其他字符的排列個數(shù)+1。也就是固定一個字符串之后，之后再將問題變小，只需求出后面子串的排列個數(shù)就可以得出結(jié)果，當(dāng)然第一時間想到的就是遞歸的算法了。下面這張圖很清楚的給出了遞歸的過程：
? ? 很明顯，遞歸的出口，就是只剩一個字符的時候，遞歸的循環(huán)過程，就是從每個子串的第二個字符開始依次與第一個字符交換，然后繼續(xù)處理子串。
代碼：
importjava.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class Solution {
????public static void main(String[] args) {
????????Solution p = new Solution();
????????System.out.println(p.Permutation("abc").toString());
????}
? ?public ArrayList Permutation(String str) {
????????List res = new ArrayList<>();
????????if(str != null&& str.length() > 0) {
????????????PermutationHelper(str.toCharArray(), 0, res);
????????????Collections.sort(res);
????????}
????????return(ArrayList)res;
????}
????public void PermutationHelper(char[] cs, int i, List list) {
????????if(i == cs.length - 1) {
????????????String val = String.valueOf(cs);
????????????if(!list.contains(val))
????????????????list.add(val);
????????} else{
????????????for(int j = i; j < cs.length; j++) {
????????????????swap(cs, i, j);
????????????????PermutationHelper(cs, i+1, list);
????????????????swap(cs, i, j);
????????????}
????????}
????}
????publicvoidswap(char[] cs, inti, intj) {
????????chartemp = cs[i];
????????cs[i] = cs[j];
????????cs[j] = temp;
????}
}
? ? 此處使得排列不重復(fù)使用的方法是判斷：???if(!list.contains(val))。
? ? 還有一個問題要注意，就是如果字符串中有重復(fù)的字符串。由于全排列就是從第一個數(shù)字起，每個數(shù)分別與它后面的數(shù)字交換，我們先嘗試加個這樣的判斷——如果一個數(shù)與后面的數(shù)字相同那么這兩個數(shù)就不交換 了。例如abb，第一個數(shù)與后面兩個數(shù)交換得bab，bba。然后abb中第二個數(shù)和第三個數(shù)相同，就不用交換了。但是對bab，第二個數(shù)和第三個數(shù)不 同，則需要交換，得到bba。由于這里的bba和開始第一個數(shù)與第三個數(shù)交換的結(jié)果相同了，因此這個方法不行。
換種思維，對abb，第一個數(shù)a與第二個數(shù)b交換得到bab，然后考慮第一個數(shù)與第三個數(shù)交換，此時由于第三個數(shù)等于第二個數(shù)，所以第一個數(shù)就不再用與第三個數(shù)交換了。再考慮bab，它的第二個數(shù)與第三個數(shù)交換可以解決bba。此時全排列生成完畢！
這樣，我們得到在全排列中去掉重復(fù)的規(guī)則：
去重的全排列就是從第一個數(shù)字起，每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
