[[428071]]

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

示例:

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

思路

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

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

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

因為一些問題能暴力搜出來就已經(jīng)很不錯了!

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

全排列

回溯三部曲

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

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

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

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

全排列

代碼如下：

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

• 遞歸終止條件

全排列

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

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

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

代碼如下：

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

• 單層搜索的邏輯

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

因為排列問題，每次都要從頭開始搜索，例如元素1在[1,2]中已經(jīng)使用過了，但是在[2,1]中還要再使用一次1。

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

代碼如下：

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<vector<int>> result; 
    vector<int> path; 
    void backtracking (vector<int>& nums, vector<bool>& used) { 
        // 此時說明找到了一組 
        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<vector<int>> permute(vector<int>& nums) { 
        result.clear(); 
        path.clear(); 
        vector<bool> used(nums.size(), false); 
        backtracking(nums, used); 
        return result; 
    } 
}; 

總結(jié)

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

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

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

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