C++回溯算法中的全排列問題怎么解決

本文小編為大家詳細介紹“C++回溯算法中的全排列問題怎么解決”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++回溯算法中的全排列問題怎么解決”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

一、全排列

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

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

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

對于全排列問題，模板是設置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++回溯算法中的全排列問題怎么解決”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。