前言

給定一個字符串，輸出該字符串中字符的所有排列。例如，輸入字符串"abc"，則輸出由字符a、b、c所能排列出來的所有字符串abc、acb、bac、bca、cab、cba。

本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發者閱讀本文。

實現思路

相信很多開發者看到這個問題都會腦子一片空白，找不到入手之處。那我們就嘗試下把這個復雜的問題分解成小問題，比如，我們把一個字符串看成兩部分組成：

• 第一部分是當前需要進行組合的元素
• 第二部分是剩余的元素（除去當前元素）

如下圖所示，我們從字符串的起始部位開始分析。

• 第一輪：

• 我們取出第1個字符"c"，當前需要進行組合的字符是"a"，拼接后，我們得到了"ac"
• 緊接著，我們取出剩余字符中的最后一個字符"b"，當前需要進行組合的字符是"ac"，拼接后，我們就得到了"acb"。剩余字符為空，我們就得到了第二個組合 ?acb?
• 剛開始的時候，需要進行組合的字符是空字符，剩余的字符就是"abc"
• 緊接著，我們取出剩余字符的第0號位置的字符"a"作為當前需要進行組合的字符，剩余的字符就為"bc"
• 隨后，我們再取出剩余字符的第0號位置的字符"b"，上一步我們得到的需要組合的字符是"a"，把上一步得到的字符與現在取出的字符進行拼接，我們就得到了"ab"，剩余的字符為"c"
• 最后，我們取出剩余字符中最后一個字符"c"，上一步我們得到的組合是"ab"，將其拼接后，我們得到了"abc"。剩余字符為空，我們就得到了第一個組合 ?abc?
• 我們在第二步的時候，剩余字符總共有兩個字符"bc"，上面我們只取出了第0個字符進行組合，我們還需要取出它的其他字符完成組合。
• 至此，我們已經訪問了所有位置的剩余字符訪問，本輪任務執行完成

• 第二輪：

• 取出第1個字符"c"，當前需要進行組合的字符是"b"。拼接后，我們得到了"bc"，剩余的字符為"a"

• 取出最后一個剩余字符"a"，當前需要進行組合的字符是"bc"。拼接后，我們得到了"bca"，剩余字符為空，我們就得到了第四個組合 ?bca?

• 
  

  同樣的，剛開始我們需要進行組合的字符為空，剩余的字符為"abc"

  
  

• 
  

  緊接著，我們取出剩余字符的第1號位置的字符"b"作為當前需要進行組合的字符，剩余的字符就為"ac"。

  
  

• 
  

  取出剩余字符的第0號元素"a"，上一步我們得到的需要進行組合的字符為"b"，將他們拼接后，得到了"ba"，剩余的字符為"c"

  
  

• 
  

  繼續去除最后一個剩余字符"b"，上一步我們得到的需要進行組合的字符為"ba"，拼接后，我們得到了"bac"，剩余字符為空，我們就得到了第三個組合 ?bac?

  
  

• 
  

  同樣的，我們在第二步的時候，剩余字符中有多個元素，我們只取了第0號位置的元素，需要把其他的字符也取出來完成組合

  
  

• 
  

  至此，我們訪問完了所有位置的剩余字符，本輪任務執行完成

  
  

• 
  

  第三輪，分析到這里我相信大家已經找到了規律，此處的分析就交給讀者來完成，幫助你更好的理解這個規律??。

  
  

image-20230220073230627

總結思路

通過上面的分析，相信很多開發者已經聯想到了回溯算法。沒錯，這就是最典型的回溯算法，具體的實現思路為：

• 回溯函數接受2個參數：當前需要進行組合的字符、剩余字符
• 遞歸的基線條件為：剩余字符為空
• 遍歷剩余字符

• 將當前需要進行組合的字符與當前遍歷到的字符進行拼接，得到回溯函數的第1個參數
• 從剩余字符中除去剛才已經拼接了的字符，將剩下的字符進行拼接，得到回溯函數的第2個參數
• 兩個參數都得到后，開始遞歸調用回溯函數

• 遍歷到剩余字符的末尾后，我們就得到了這個問題的解（找到了目標字符串的所有字符排列）

實現代碼

思路捋清楚之后，很容易就能將其轉換為代碼。

• 回溯函數的實現

/**
   * 使用回溯實現對字符的排列
   * @param current 當前字符
   * @param remaining 剩余的字符
   * @private
   */
  private backtrack(current: string, remaining: string) {
    // 基線條件：剩余字符為空時則代表已經完成本輪排列
    if (remaining.length === 0) {
      this.result.push(current);
      return;
    }
    // 用Set結合來標記當前字符是否已經組合過
    const usedChars = new Set<string>();
    for (let i = 0; i < remaining.length; i++) {
      // 字符已經出現過則跳過本輪循環
      if (usedChars.has(remaining[i])) {
        continue;
      }
      usedChars.add(remaining[i]);
      const nextCurrent = current + remaining[i];
      // 除當前字符外的字符拼到一起
      const nextRemaining = remaining.slice(0, i) + remaining.slice(i + 1);
      this.backtrack(nextCurrent, nextRemaining);
    }
  }

• 獲取字符串中所有字符的排列

public permute(str: string): Array<string> {
    this.result = [];
    this.backtrack("", str);
    return this.result;
  }

注意：字符串中如果有重復字符，會造成重復的排列組合。因此，我們在實現回溯函數的時候，用Set集合對當前遍歷到的字符進行了標記，如果已經存在了就會跳過本輪循環，繼續找下一個字符。

測試用例

我們用文章開頭所列舉的例子來校驗下上述代碼能否正確給出結果。

const arrayOfStrings = new ArrayOfStrings();
const result = arrayOfStrings.permute("abc");
console.log(result);