求全組合

例如，在[1,n]這n個數(shù)中，選擇k個數(shù)，那么總共有多少種可能？把這些可能都列出來?
我們在數(shù)學(xué)上，$C_n^k$種可能一一列舉出來。
計算機(jī)在解決這個問題時,我們采用的時DFS的思路

思路一:全排列剪枝

組合問題實(shí)際是排列問題在不考慮數(shù)字順序的情況
在[1,n]這n個數(shù)中,選擇k個數(shù),那么我們首先選擇第一個數(shù),然后選擇第二個數(shù),然后選擇第三個數(shù),直到選擇到第k個數(shù)。
既然組合問題它不考慮數(shù)字的順序,那么我們不妨永遠(yuǎn)保持它從小到大,即在選擇數(shù)的時候,要求這個數(shù)要比已經(jīng)選擇的所有數(shù)大。

vector<int> temp;vector<vector<int>> results;void dfs(int n,int k,int level){//level表示目前在取第幾個數(shù)if(level==k+1){results.push_back(temp);return;}int i=1;if(temp.size()!=0){i=temp[temp.size()-1]+1;//即temp種最大的數(shù)+1}while(i<=n){temp.push_back(i);dfs(n,k,level+1);temp.pop_back();i++;}}

思路二:

我們同樣采用DFS算法,但是我們的思路是,依次考察1,2,…,k這些數(shù),分別考慮它們在不在結(jié)果中,這種算法更加優(yōu)越,因為它無形中就暗含著結(jié)果中數(shù)字是從小到大排序的。

vector<int> temp;vector<vector<int>> results;void dfs(int n,int k,int cur){//我們的思路是考察cur這個數(shù)是不是在temp中，一種是在，一種是不在//考察cur這個數(shù)時,[1,cur-1]都已經(jīng)考察完了if(temp.size()==k){results.push_back(temp);return;}//如果temp中的數(shù)的個數(shù)加上剩下沒考慮的數(shù) 的個數(shù)之和小于k，這種就沒必要選取了if(n-cur+1+temp.size()<k){return;}//cur在temp中temp.push_back(cur);dfs(n,k,cur+1);temp.pop_back();//cur不在temp中dfs(n,k,cur+1);}

總結(jié)

以上是生活随笔為你收集整理的C++求全组合的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。