C語(yǔ)言回溯法實(shí)現(xiàn)組合數(shù) 從N個(gè)數(shù)中選擇M個(gè)數(shù)

2020-05-23 13:30:19

字體：大中小

供稿：網(wǎng)友

前言

在平時(shí)的算法的題目中，時(shí)常會(huì)遇到組合數(shù)相關(guān)的問(wèn)題，暴力枚舉。在N個(gè)數(shù)中挑選M個(gè)數(shù)出來(lái)。利用for循環(huán)也可以處理，但是可拓展性不強(qiáng)，于是寫(xiě)這個(gè)模板供以后參考。

兩個(gè)函數(shù)和全局變量可以直接用。

代碼：

#include<iostream>#include<cstdio> #define N 10    //被選擇的數(shù)目#define M 5    //要選出來(lái)的數(shù)目 using namespace std;int vis[N+1];    //標(biāo)志，int ans=0;    //含有的組合數(shù) 的數(shù)量int num[M+1];    //選出來(lái)的數(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個(gè)數(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);    //回溯開(kāi)始	cout<<endl<<ans;	return 0;}

C語(yǔ)言,回溯法,組合數(shù)