前言
在平時的算法的題目中，時常會遇到組合數相關的問題，暴力枚舉。在N個數中挑選M個數出來。利用for循環也可以處理，但是可拓展性不強，于是寫這個模板供以后參考。
兩個函數和全局變量可以直接用。
代碼：
#include<iostream>#include<cstdio> #define N 10 //被選擇的數目#define M 5 //要選出來的數目 using namespace std;int vis[N+1]; //標志，int ans=0; //含有的組合數 的數量int num[M+1]; //選出來的數放在num數組里面 void solve() { //在solve函數里面處理 for(int i=1; i<M+1; i++) cout<<num[i]<<" "; cout<<endl;} void dfs(int index) { //挑選的第index+1個數 if(index == M) { solve(); ans++; return ; } for(int i=num[index]+1; i<N+1; i++) { if(!vis[i]) { vis[i] = 1; num[index+1] = i; dfs(index+1); vis[i] = 0; } }} int main(){ dfs(0); //回溯開始 cout<<endl<<ans; return 0;}
可以發現利用回溯法挑選的有一個優勢在于，輸出的數組是經過排序的。
新聞熱點
疑難解答
