本題主要在於對回溯的理解，最佳化時可以結合 java 特性，以及排列的一些知識。
原題
輸入一個字串，打印出該字串中字元的所有排列。
你可以以任意順序返回這個字串陣列，但裡面不能有重複元素。
示例：
輸入：s = “abc”輸出：［“abc”，“acb”，“bac”，“bca”，“cab”，“cba”］
限制：
1 <= s 的長度 <= 8
原題url：https：//leetcode-cn。com/problems/zi-fu-chuan-de-pai-lie-lcof
解題
回溯
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
大家在解決經典的八皇后問題時，大多都會採用回溯進行解決。
本問題其實就是求所有字元的排列組合，針對這種問題，也可以利用回溯進行解決，但要求不能重複，因此需要進行剪枝。
比如字串 abc ，如果讓我們求所有排列，肯定是：
先固定第 1 位，從 a 、b 、 c 中選一個，比如 a。
在以 a 為第 1 位的前提下，固定第 2 位，從 b 、 c 中選一個，比如 b。
此時第 3 位也沒有可以選擇的餘地了，只剩下 c，這一步就走完了。
退回第 2 步，依舊在第 2 位，這次選擇 c 。
此時第 3 位也沒有可以選擇的餘地了，只剩下 b，這一步也走完了。
退回第 1 步。
從上面，你可以總結出，正常的回溯，就是先走一條路，當結束後，退回上一步繼續走，反覆執行，直至退無可退，結束流程。
我們可以發現，最終是沒有可以選擇的餘地，這在程式裡可以理解為，執行到下一位時，不能使用之前使用過的資料，因此會涉及到字元交換。
但因為會進行回溯，所以數字可以在回溯後再換回去，從而不影響下一次的回溯。
那什麼叫剪枝呢？就是要排除一些情況，針對本題，就是要排除重複的情況。
也就是在同一位置，不能出現兩次相同的字元，因為第 2 次出現時，之前肯定已經針對這種情況，所有路線都已經走過了。
因此可以聯想到使用集合，儲存當前位置出現過的字元，如果重複，就可以直接跳過。
接下來我們看看程式碼：
class Solution { char［］ array； List
提交OK。
分析一下複雜度：
時間複雜度 O（N！） ： 這個比較好理解，長度為 N 的字串，需要計算的次數是： N * （N - 1） * （N - 2） * 。。。 * 2 * 1，結果也就是 N！ 。
空間複雜度 O（N^2） ： 需要藉助的額外空間，也就是那個保證不會重複所使用到的set，它所儲存的總量，最差情況下，長度為 N 的字串中，所有字元各不相同，也就需要 N + （N - 1） + （N - 2） * 。。。 * 2 * 1，結果也就是 N^2。
java 最佳化
針對上面程式碼中出現的 char［］ 轉 String，可以使用String。valueOf（char［］）方法進行最佳化，因為該方法，最終會使用System。arrayCopy方法，該方法屬於native方法，更加高效。
至於最終，將 list 轉 array 的過程，可以用list。toArray（String［］）做寫法上的簡化，效能上倒並沒有什麼提升。
最佳化後的程式碼為：
class Solution { char［］ array； List
繼續最佳化
其實到了，如果想進一步最佳化的話，可以針對 list 轉 array 這裡。
因為我們使用的是 LinkedList，內部儲存的 String 物件在物理上是不連續的，在最後遍歷時會相對比較耗時。
如果我們一開始就可以求出所有該字串所能獲得的所有不重複字串的總個數的話，就可以提前構造一個 array，不需要在最後又遍歷一次 list 了。
那麼如何求出有重複字元的所有排列呢？假設是字串aabbc，其求法為：
假設先排 a ，一共 5 個位置，選 2 個位置，C（5， 2） = （5 * 4） / （2 * 1） = 10。
再排 b ，剩下 3 個位置裡，選 2 個位置，C（3， 2） = （3 * 2） / （2 * 1） = 3。
最後排 c ，剩下 1 個位置裡，選 1 個位置，C（1， 1） = 1。
綜上，一共有10 * 3 * 1 = 30種排列。
接下來看看程式碼：
class Solution { char［］ array； String［］ result； int resultIndex = 0； public String［］ permutation（String s） { array = s。toCharArray（）； // 求出一共有多少種可能 int totalCount = calculate（）； result = new String［totalCount］； // 回溯 backtrack（0）； // 賦值給陣列 return result； } private int calculate（） { // 各字元出現的次數，預設只會出現26個英文字母 int［］ countArray = new int［26］； for （char temp ： array） { countArray［temp - ‘a’］ += 1； } // 統計總次數 int length = array。length； int totalCount = 1； for （int count ： countArray） { if （count == 0） { continue； } // 求排列 totalCount *= cc（length， count）； length -= count； } return totalCount； } private int cc（int total， int count） { // 如果count超過total的一半，則換成 （total - count），因為在排列中，C（5， 4） = C（5， 1） if （count > total / 2） { count = total - count； } // 分別求分子、分母 int result = 1； int result1 = 1； for （int i = 0； i < count； i++） { result *= （total - i）； result1 *= （count - i）； } return result / result1； } private void backtrack（int index） { // 如果是最後一個位置，就可以新增進result中 if （index == array。length - 1） { result［resultIndex++］ = String。valueOf（array）； return； } // 預設只會出現26個英文字母 boolean［］ exists = new boolean［26］； for （int i = index； i < array。length； i++） { // 保證不會重複 if （exists［array［i］ - ‘a’］） { continue； } exists［array［i］ - ‘a’］ = true； // 交換兩者的位置 swap（index， i）； // 固定下一個位置，繼續尋找 backtrack（index + 1）； // 還原兩者的位置 swap（i， index）； } } private void swap（int index， int newIndex） { char temp = array［index］； array［index］ = array［newIndex］； array［newIndex］ = temp； }}
提交OK，其執行時間最短，因此認為最佳化是有效的。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。本題主要在於對回溯的理解，最佳化時可以結合 java 特性，以及排列的一些知識。
有興趣的話可以訪問我的部落格或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https：//death00。github。io/
公眾號：健程之道
