C++回溯算法中的全排列問題分析探討
更新時間：2023年03月15日 09:06:01 作者：清風(fēng)何渡
遞歸中遇到一個問題全排列的問題，我看見回溯特別神奇，特此記錄一下。對比一下深度優(yōu)先搜索與廣度優(yōu)先搜索，個人感覺這里的回溯像是一種遞歸樹中的深度優(yōu)先搜索的算法，他不斷構(gòu)造往下延伸的深度，使其達(dá)到完全編列
一、全排列
全排列的特點就是：解放了index（每次遍歷都從0開始），但是解放index的同時，又捆綁了used數(shù)組，記錄已經(jīng)出現(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ū)別在于輸入樣例為可重復(fù)序列，且要求輸出樣例不重復(fù)
對于全排列問題，模板是設(shè)置used數(shù)組，只有used[i]==0時，才能選擇該元素
對于去重問題，模板是先對nums排序，再判斷nums[i]與nums[i-1]是否相等
根據(jù)全排列問題模板，設(shè)置used數(shù)組，只有used[i]==0時才可以選擇
根據(jù)去重模板，先對nums排序，再判斷nums[i]與nums[i-1]是否相等
但是全排列的去重沒那么簡單，因為全排列i是從0開始遍歷，因此還要記錄同一層當(dāng)前已經(jīng)訪問到哪兒了，同一層不可以重復(fù)，但是同一樹枝可以重復(fù)
但是不必再設(shè)置index，因為used數(shù)組可以兼任這個功能
如果used[i-1]==1，說明在同一個樹枝訪問過nums[i-1]，同一樹枝可以重復(fù)
如果used[i-1]==0，說明在同一層訪問過nums[i-1]，同一層不可以重復(fù)
很繞~
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;
}
};到此這篇關(guān)于C++回溯算法中的全排列問題分析探討的文章就介紹到這了,更多相關(guān)C++回溯算法全排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了利用C語言實現(xiàn)三子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細(xì)介紹了Qt簡單實現(xiàn)密碼器控件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家詳細(xì)介紹了C語言二分查找法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了C++的.cpp文件運行全過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要給大家介紹了關(guān)于C語言堆棧幀的相關(guān)資料,堆棧幀 (stack frame)( 或活動記錄 (activation Tecord)) 是一塊堆棧保留區(qū)域,用于存放被傳遞的實際參數(shù)、子程序的返回值、局部變量以及被保存的寄存器,需要的朋友可以參考下
2021-08-08 
這篇文章主要介紹了C++ IO流的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下
2020-08-08 
這篇文章主要介紹了C++中的5個存儲類的作用,存儲類是管理對象的生存期、鏈接和內(nèi)存位置的類型說明符,需要的朋友可以參考下
2016-05-05 
大家好，本篇文章主要講的是關(guān)于C語言動態(tài)內(nèi)存管理介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下
2022-01-01 
實例講解C++設(shè)計模式編程中State狀態(tài)模式的運用場景
這篇文章主要介紹了實例講解C++設(shè)計模式編程中State狀態(tài)模式的運用場景,文章最后的適用性部分則介紹了一些State模式善于處理的情況,需要的朋友可以參考下
2016-03-03