溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
在平時的算法的題目中，時常會遇到組合數相關的問題，暴力枚舉。在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;
}
可以發現利用回溯法挑選的有一個優勢在于，輸出的數組是經過排序的。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
