原文鏈接

DFS解決全排列問題，從一道奧數(shù)題開始說起。http://www.itdecent.cn/p/897f2a9e33cd

總結(jié)

有關(guān)全排列的題目可以通過DFS來解決。

• 最簡單的例子
  • 題目：有數(shù)字1-9，求其全排列
  • 分析：
    想象有九個空位a[9]，現(xiàn)在第一個空位上填上一個數(shù)字，有多種選擇，假設(shè)a[0] = 1；
    接下來在第二個空位上繼續(xù)填數(shù)字，要求不與之前填過的數(shù)字相同（用book標(biāo)記），則還剩下8個數(shù)字可以選擇，假設(shè)a[1] = 2；
    依次類推，全部填滿，打印。
    之后要退回一位，恢復(fù)book標(biāo)記，選擇其他數(shù)字，向下填空。
  • 偽代碼

void dfs(int step){ //step表示當(dāng)前要處理的盒子
      if(step == n+1){
            //輸出排列
            for(i = 1; i <= n; i++)
                  printf("%d", a[i]);
            printf("\n");
            return;
      }
      for(int i = 1; i <= n; i++){
      if(book[i] == 0){
            a[step] = i;   //將i放入第step個空位
            book[i] = 1; // i已經(jīng)被使用了
            dfs(step+1); //向下調(diào)用
            book[i] = 0; // 非常重要，收回該空位中的數(shù)字才能進(jìn)行下一次嘗試。
      }
  }
}

• DFS框架
  由上述分析，可發(fā)現(xiàn)過程類似DFS框架。DFS核心在于，對于每一個中可能性都嘗試一遍，確定當(dāng)前位的數(shù)字后，再以同樣的方式調(diào)用下一位。
  偽代碼：

void dfs(int step){
      *判斷結(jié)束邊界*
        嘗試每一種可能 for(i = 1; i <= n; i++){
              嘗試下一步 dfs(step + 1);
        }
    return; 
}

• 其他變形
  • 判斷每一種可能——給定數(shù)組，空位選擇不重復(fù)
    1-9可能變形為給定數(shù)組，則同樣可以通過索引和book來選擇數(shù)據(jù)；此外，還可以用swap來代替book，對于給定數(shù)組，在指定位可以與后面的數(shù)字交換，同樣可以實現(xiàn)選擇的功能。
    例子： [http://blog.csdn.net/ns_code/article/details/26509459
  • 重復(fù)數(shù)組中有重復(fù)的，求不同的排列
    額外開啟一個unsorted_set用于記錄當(dāng)前位已經(jīng)選擇過的數(shù)字，如果再次遇到已經(jīng)選擇過的數(shù)字，則跳過。