C++回溯算法中的全排列問題分析探討

更新時間：2023年03月15日 09:06:01 作者：清風何渡

遞歸中遇到一個問題全排列的問題，我看見回溯特別神奇，特此記錄一下。對比一下深度優(yōu)先搜索與廣度優(yōu)先搜索，個人感覺這里的回溯像是一種遞歸樹中的深度優(yōu)先搜索的算法，他不斷構造往下延伸的深度，使其達到完全編列

一、全排列

全排列的特點就是：解放了index（每次遍歷都從0開始），但是解放index的同時，又捆綁了used數組，記錄已經出現(xiàn)過的元素

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    int used[7]={0};
    void backtracking(vector<int>& nums){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==1)
                continue;
            path.push_back(nums[i]);
            used[i]=1;
            backtracking(nums);
            used[i]=0;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return result;
    }
};

二、全排列II

本題與全排列唯一不同在于需要去重這題與上一題唯一區(qū)別在于輸入樣例為可重復序列，且要求輸出樣例不重復

對于全排列問題，模板是設置used數組，只有used[i]==0時，才能選擇該元素

對于去重問題，模板是先對nums排序，再判斷nums[i]與nums[i-1]是否相等

根據全排列問題模板，設置used數組，只有used[i]==0時才可以選擇

根據去重模板，先對nums排序，再判斷nums[i]與nums[i-1]是否相等

但是全排列的去重沒那么簡單，因為全排列i是從0開始遍歷，因此還要記錄同一層當前已經訪問到哪兒了，同一層不可以重復，但是同一樹枝可以重復

但是不必再設置index，因為used數組可以兼任這個功能

如果used[i-1]==1，說明在同一個樹枝訪問過nums[i-1]，同一樹枝可以重復

如果used[i-1]==0，說明在同一層訪問過nums[i-1]，同一層不可以重復

很繞~

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    int used[9]={0};
    void backtracking(vector<int>& nums){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)
                continue;
            if(used[i]==0){
                path.push_back(nums[i]);
                used[i]=1;
                backtracking(nums);
                used[i]=0;
                path.pop_back();
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backtracking(nums);
        return result;
    }   
};

到此這篇關于C++回溯算法中的全排列問題分析探討的文章就介紹到這了,更多相關C++回溯算法全排列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: