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