C語(yǔ)言回溯法 實(shí)現(xiàn)組合數(shù) 從N個(gè)數(shù)中選擇M個(gè)數(shù)
更新時(shí)間：2018年08月11日 16:19:42 作者：Alger_jhun
在平時(shí)的算法的題目中，時(shí)常會(huì)遇到組合數(shù)相關(guān)的問(wèn)題，暴力枚舉。在N個(gè)數(shù)中挑選M個(gè)數(shù)出來(lái)。利用for循環(huán)也可以處理，但是可拓展性不強(qiáng)，于是寫(xiě)這個(gè)模板供以后參考
前言
在平時(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;
}
可以發(fā)現(xiàn)利用回溯法挑選的有一個(gè)優(yōu)勢(shì)在于，輸出的數(shù)組是經(jīng)過(guò)排序的。
相關(guān)文章
這篇文章主要介紹了VC中刪除類(lèi)的兩種操作方法,較為詳細(xì)的描述了在VC中實(shí)現(xiàn)刪除類(lèi)的具體步驟,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了使用WindowsAPI獲取錄音音頻的方法,非常實(shí)用的功能,需要的朋友可以參考下2014-08-08
C語(yǔ)言位段(位域)機(jī)制結(jié)構(gòu)體的特殊實(shí)現(xiàn)及解析
這篇文章主要為大家介紹了C語(yǔ)言位段位域機(jī)制結(jié)構(gòu)體的特殊實(shí)現(xiàn)講解有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-02-02
C++制作鼠標(biāo)連點(diǎn)器實(shí)例代碼
大家好，本篇文章主要講的是C++制作鼠標(biāo)連點(diǎn)器實(shí)例代碼，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C++深入分析數(shù)據(jù)在內(nèi)存中的存儲(chǔ)形態(tài)
使用編程語(yǔ)言進(jìn)行編程時(shí)，需要用到各種變量來(lái)存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個(gè)變量時(shí)，就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類(lèi)型的信息，操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類(lèi)型，來(lái)分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2023-01-01
這篇文章主要介紹了C語(yǔ)言中的各種文件讀寫(xiě)方法小結(jié),是C語(yǔ)言入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-07-07
這篇文章主要介紹了C++存儲(chǔ)方案和動(dòng)態(tài)分配，2021-12-12
C 語(yǔ)言中的多維數(shù)組（multidimensional array）其實(shí)就是元素為數(shù)組的數(shù)組。多維指針根據(jù)聲明的維數(shù)需要進(jìn)行多次地址轉(zhuǎn)換才能夠取到目標(biāo)數(shù)據(jù)。但指針作為數(shù)據(jù)變量，可以多次賦值，使其成為對(duì)數(shù)組操作訪問(wèn)的一大利器，所以指針和數(shù)組的結(jié)合才是重中之重2022-04-04
C語(yǔ)言菜鳥(niǎo)基礎(chǔ)教程之常量和變量
在C語(yǔ)言中，常量和變量都是可以用來(lái)存儲(chǔ)和表示數(shù)據(jù)的，常量值在程序執(zhí)行的過(guò)程中是不可變的，而變量是可變的2017-10-10
在C++的STL中,vector是一個(gè)動(dòng)態(tài)數(shù)組,可以在運(yùn)行時(shí)調(diào)整大小,本文介紹了vector的初始化、元素訪問(wèn)、修改、迭代器操作、容量管理以及性能優(yōu)化技巧,通過(guò)這些操作,可以有效地使用vector管理數(shù)據(jù),本文介紹C++ vector 操作,感興趣的朋友一起看看吧2024-10-10