dfs+剪枝解决组合问题

组合题是编程中很经典的递归问题，也很难理解...

题目描述：

初学时画树帮助理解

伪代码：

自己写的代码：

#include
using namespace std;

int zuhe[100];//保存查到的序列
int m,k;//从1到m查出k个数后输出

void dfs(int k,int start,int done){ //start是开始查的点,done是已经查了多少个了
    if(done == k){ //查到了k个数，输出
        for(int i = 1; i <= k;i++){
            cout << zuhe[i]<<" ";
        }
        cout << endl;
        return;
    }
    for(int i = start; i <=m;i++){
        zuhe[done+1] = i;
        dfs(k,i+1,done+1);//比如i=1时，下个查询点应该是i+1
    }
}


int main()
{

    cin >> m>>k;
    dfs(k,1,0);


    return 0;
}