寫在前面：

題目鏈接：LeetCode.46. 全排列
編程語言：C++
題目難度：中等

一、題目描述

給定一個不含重復數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2：

輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例3：

輸入：nums = [1]
輸出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整數(shù) 互不相同

二、解題思路

2.1 回溯法

我們再次用 樹狀思維邏輯，從根出發(fā)，葉子節(jié)點為結(jié)果集之一
示例：

這個樹像是做一個減法：
從這個集合里，不斷的取出一個數(shù)字，再將這個數(shù)字從當前集合中刪除掉，剩下的元素做下一次的可選值

這里我曾經(jīng)想用一個set 保存這些值，每選一個數(shù)字，就從set 中 erase 掉這個數(shù)字，然后把這個 set 再做下一次選擇的集合，問題是每次需要初始化為一個 全集，似乎有點麻煩，這樣我們換一種思路：

維護一個 vector<bool> isUsed 數(shù)組，開始都初始化為 false ,代表每個元素都沒有用過，每當選擇其中一個元素，將該元素置為 true 代表用過了，下一次選擇的時候，只選擇 值為 false 的元素

這里的下一次當然要使用遞歸，一直遞歸到 結(jié)果 剛好 == nums.size() , 表示這一組排列組合已經(jīng)完成了，那么如何回溯呢？

代碼實現(xiàn)：

class Solution {
public:
    vector<vector<int>> vctResult;//所有結(jié)果集
    vector<int> vctTemp;//子集
    void back(vector<int>& nums, vector<bool>& isUsed)
    {
        if(vctTemp.size() == nums.size())
        {
            vctResult.push_back(vctTemp);
            return;
        }
        for(int i = 0; i < nums.size();i++)
        {
            if(isUsed[i] == false)
            {
                vctTemp.push_back(nums[i]);//選擇該數(shù)字
                isUsed[i] = true;
                back(nums, isUsed);//遞歸繼續(xù)往下選擇
                isUsed[i] = false;//回溯
                vctTemp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> isUsed(nums.size(), false);//每個元素的使用情況
        back(nums, isUsed);
        return vctResult;
    }
};

其實回溯代碼也是有一個套路和模板的大致樣子的，例如上述題目：

result //結(jié)果
def backtrack(路徑, 選擇列表):
    if 滿足結(jié)束條件:
        reslut.push_back(結(jié)果集)
        return
    
    for 選擇列表:
        做選擇
        backtrack(路徑, 選擇列表)
        撤銷選擇

三、完整代碼

class Solution {
public:
    vector<vector<int>> vctResult;//所有結(jié)果集
    vector<int> vctTemp;//子集
    void back(vector<int>& nums, vector<bool>& isUsed)
    {
        if(vctTemp.size() == nums.size())
        {
            vctResult.push_back(vctTemp);
            return;
        }
        for(int i = 0; i < nums.size();i++)
        {
            if(isUsed[i] == false)
            {
                vctTemp.push_back(nums[i]);//選擇該數(shù)字
                isUsed[i] = true;
                back(nums, isUsed);//遞歸繼續(xù)往下選擇
                isUsed[i] = false;//回溯
                vctTemp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> isUsed(nums.size(), false);//每個元素的使用情況
        back(nums, isUsed);
        return vctResult;
    }
};

運行結(jié)果：
文章來源地址http://www.zghlxwxcb.cn/news/detail-462699.html

到了這里，關于LeetCode.46. 全排列(回溯法入門)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！