题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

样例

输入样例:

5 3
输出样例:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

算法1

dfs

脑中要有树

C++ 代码

#include<iostream>
using namespace std;

const int N = 30;

int n, m;

int way[N];

void dfs(int u, int start){ //已经选了u个数,从start开始选

    if(u == m + 1){
        for(int i = 1; i <= m; i++) cout << way[i] << " ";
        cout << endl;
        return ;
    }

    for(int i = start; i <= n; i++){
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0; //恢复现场
    }
}


int main(){

    cin >> n >> m;

    dfs(1, 1); //第一位从1开始

    return 0;
}

算法2

优化dfs, 剪枝

C++ 代码

#include<iostream>
using namespace std;

const int N = 30;

int n, m;

int way[N];

void dfs(int u, int start){

    if(u + n - start < m) return ;
    // if (u - 1 + n - start + 1 < m) return; // 前面已有u-1个数,后面最多有n-start+1个数

    if(u == m + 1){
        for(int i = 1; i <= m; i++) cout << way[i] << " ";
        cout << endl;
        return ;
    }

    for(int i = start; i <= n; i++){
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0; //恢复现场
    }
}


int main(){

    cin >> n >> m;

    dfs(1, 1); //第一位从1开始

    return 0;
}