文章目錄

• • • 題目解答
    • 題目來(lái)源

題目解答

分析：
dfs求全排列，這里是用二進(jìn)制狀態(tài)壓縮進(jìn)行優(yōu)化，二進(jìn)制狀態(tài)壓縮，顧名思義，每個(gè)狀態(tài)是用二進(jìn)制的某一位表示。這里的體現(xiàn)是state這個(gè)狀態(tài)，它的每一位代表1個(gè)數(shù)被選了。比如state = 5，二進(jìn)制表示是101，這就表示1和3被用了，2卻沒(méi)有被用。

ac代碼

#include<bits/stdc++.h> using namespace std;int n; vector<int> path;// state的二進(jìn)制 表示哪些數(shù)被用過(guò)了，比如 state = 3，二進(jìn)制是11，表示1和2用過(guò)了 void dfs(int u , int state){if( u == n){for(auto x : path) cout << x << " ";cout << endl;return;}// 當(dāng)前位置該選哪個(gè)數(shù)for(int i = 0; i < n; i++){// 當(dāng)前i沒(méi)用過(guò)，就把它加到path中if(!(state >> i & 1)){path.push_back(i + 1);dfs( u + 1, state | 1 << i);// dfs轉(zhuǎn)移，后面表示i這位用過(guò)了// 恢復(fù)現(xiàn)場(chǎng)path.pop_back();}} }int main(){cin >> n;dfs(0, 0); }

題目來(lái)源

https://www.acwing.com/problem/content/96/

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的《算法竞赛进阶指南》打卡-基本算法-AcWing 94. 递归实现排列型枚举：dfs、二进制状态压缩的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。