給定一個(gè) 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

創(chuàng)新互聯(lián)是專業(yè)的古丈網(wǎng)站建設(shè)公司，古丈接單;提供成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行古丈網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

示例:

• 輸入: [1,2,3]
• 輸出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路

此時(shí)我們已經(jīng)學(xué)習(xí)了組合問題、 分割回文串和子集問題，接下來看一看排列問題。

相信這個(gè)排列問題就算是讓你用for循環(huán)暴力把結(jié)果搜索出來，這個(gè)暴力也不是很好寫。

所以正如我們在關(guān)于回溯算法，你該了解這些!所講的為什么回溯法是暴力搜索，效率這么低，還要用它?

因?yàn)橐恍﹩栴}能暴力搜出來就已經(jīng)很不錯(cuò)了!

我以[1,2,3]為例，抽象成樹形結(jié)構(gòu)如下：

全排列

回溯三部曲

• 遞歸函數(shù)參數(shù)

首先排列是有序的，也就是說[1,2] 和[2,1] 是兩個(gè)集合，這和之前分析的子集以及組合所不同的地方。

可以看出元素1在[1,2]中已經(jīng)使用過了，但是在[2,1]中還要在使用一次1，所以處理排列問題就不用使用startIndex了。

但排列問題需要一個(gè)used數(shù)組，標(biāo)記已經(jīng)選擇的元素，如圖橘黃色部分所示:

全排列

代碼如下：

 
 
 
 
  
  
  
  
vector> result; 
  
  
  
  
vector path; 
  
  
  
  
void backtracking (vector& nums, vector& used) 
 
 
 

• 遞歸終止條件

全排列

可以看出葉子節(jié)點(diǎn)，就是收割結(jié)果的地方。

那么什么時(shí)候，算是到達(dá)葉子節(jié)點(diǎn)呢?

當(dāng)收集元素的數(shù)組path的大小達(dá)到和nums數(shù)組一樣大的時(shí)候，說明找到了一個(gè)全排列，也表示到達(dá)了葉子節(jié)點(diǎn)。

代碼如下：

 
 
 
 
  
  
  
  
// 此時(shí)說明找到了一組 
  
  
  
  
if (path.size() == nums.size()) { 
  
  
  
  
    result.push_back(path); 
  
  
  
  
    return; 
  
  
  
  
} 
 
 
 

• 單層搜索的邏輯

這里和組合問題、切割問題和子集問題最大的不同就是for循環(huán)里不用startIndex了。

因?yàn)榕帕袉栴}，每次都要從頭開始搜索，例如元素1在[1,2]中已經(jīng)使用過了，但是在[2,1]中還要再使用一次1。

而used數(shù)組，其實(shí)就是記錄此時(shí)path里都有哪些元素使用了，一個(gè)排列里一個(gè)元素只能使用一次。

代碼如下：

 
 
 
 
  
  
  
  
for (int i = 0; i < nums.size(); i++) { 
  
  
  
  
    if (used[i] == true) continue; // path里已經(jīng)收錄的元素，直接跳過 
  
  
  
  
    used[i] = true; 
  
  
  
  
    path.push_back(nums[i]); 
  
  
  
  
    backtracking(nums, used); 
  
  
  
  
    path.pop_back(); 
  
  
  
  
    used[i] = false; 
  
  
  
  
} 
 
 
 

整體C++代碼如下：

 
 
 
 
  
  
  
  
class Solution { 
  
  
  
  
public: 
  
  
  
  
    vector> result; 
  
  
  
  
    vector path; 
  
  
  
  
    void backtracking (vector& nums, vector& used) { 
  
  
  
  
        // 此時(shí)說明找到了一組 
  
  
  
  
        if (path.size() == nums.size()) { 
  
  
  
  
            result.push_back(path); 
  
  
  
  
            return; 
  
  
  
  
        } 
  
  
  
  
        for (int i = 0; i < nums.size(); i++) { 
  
  
  
  
            if (used[i] == true) continue; // path里已經(jīng)收錄的元素，直接跳過 
  
  
  
  
            used[i] = true; 
  
  
  
  
            path.push_back(nums[i]); 
  
  
  
  
            backtracking(nums, used); 
  
  
  
  
            path.pop_back(); 
  
  
  
  
            used[i] = false; 
  
  
  
  
        } 
  
  
  
  
    } 
  
  
  
  
    vector> permute(vector& nums) { 
  
  
  
  
        result.clear(); 
  
  
  
  
        path.clear(); 
  
  
  
  
        vector used(nums.size(), false); 
  
  
  
  
        backtracking(nums, used); 
  
  
  
  
        return result; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 

總結(jié)

大家此時(shí)可以感受出排列問題的不同：

• 每層都是從0開始搜索而不是startIndex
• 需要used數(shù)組記錄path里都放了哪些元素了

排列問題是回溯算法解決的經(jīng)典題目，大家可以好好體會(huì)體會(huì)。

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄生公眾號(hào)。

網(wǎng)頁標(biāo)題：我們一起學(xué)習(xí)排列問題！你會(huì)嗎？
地址分享：http://uogjgqi.cn/article/cdedjpd.html