[[428071]]

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

示例:

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

思路

此時我們已經學習了組合問題、 分割回文串和子集問題，接下來看一看排列問題。

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

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

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

我以[1,2,3]為例，抽象成樹形結構如下：

全排列

回溯三部曲

• 遞歸函數參數

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

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

但排列問題需要一個used數組，標記已經選擇的元素，如圖橘黃色部分所示:

全排列

代碼如下：

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

• 遞歸終止條件

全排列

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

那么什么時候，算是到達葉子節點呢?

當收集元素的數組path的大小達到和nums數組一樣大的時候，說明找到了一個全排列，也表示到達了葉子節點。

代碼如下：

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

• 單層搜索的邏輯

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

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

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

代碼如下：

for (int i = 0; i < nums.size(); i++) { 
    if (used[i] == true) continue; // path里已經收錄的元素，直接跳過 
    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里已經收錄的元素，直接跳過 
            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; 
    } 
}; 

總結

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

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

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

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄生公眾號。