打印前n个自然数选r个的所有组合。

Question

递归。书上留了个“请读者自己完成”，想了半天不会。

思路：

从1到n循环，

1.取第i个

2.在i+1后的数中取r-1个

3.合并1、2步中所取数字，得到一种组合

​
第一次尝试（3选2测试）：

#include <stdio.h>

void combination(int s, int j); //从s到n里选j个数打印出来

int n, r;

int main(void)
{
    n = 3;
    r = 2;
    combination(1, r);
    return 0;
}

void combination(int s, int j)
{
    for (int i = s; i <= n - j + 1; i++)
    {
        printf("%4d", i);
        if (j > 1)
        {
            combination(i + 1, j - 1);
        }
        else
            printf("\n");
    }
}

输出：

   1   2
   3
   2   3

错误原因：打完1之后，开始进行combination（2，1），这个函数只会打印出2、3，从而3并未和1进行合并。

解决方案：

1，（书上给出了具体方法）使用全局数组变量存储每层的i

#include <stdio.h>

void combination(int s, int j); //从s到n里选j个数打印出来

int n, r;
int arr_i[20];

int main(void)
{
    n = 5;
    r = 3;
    combination(1, r);
    return 0;
}

void combination(int s, int j)
{
    for (int i = s; i <= n - j + 1; i++)
    {
        arr_i[r - j] = i; //r-j就是i所在的层数。可理解为选出了第i个数，但还要接着选，尚未合并打印
        if (j > 1)
        {
            combination(i + 1, j - 1);
        }
        else //递归出口，若只需寻找一个数就不用再深一层了，打印出选出来的所有数即可
        {
            for (int k = 0; k < r; k++)
                printf("%4d", arr_i[k]);
            printf("\n");
        }
    }
}

2，在每层递归时打印本层i。书上没给答案，我想不出来。

​

Answer 1

#include<iostream> 
using namespace std; 
int sum[100]; 
void function(int m,int k) 
{ 
    int i,j; 
    for(i=m;i>=k;i--) 
    { 
        a[k]=i; 
        if(k>1) 
            function(i-1,k-1); 
        else 
        { 
            for(j=a[0];j>0;j--) 
                cout<<a[j]<<"\t"; 
            cout<<endl; 
        } 
    } 
} 
  
  
int main() 
{ 
    int n,r; 
    cout<<"请输入n和r的值:"<<endl; 
    cin>>n>>r; 
    if(r>n) 
        cout<<"输入n和r的值错误!"<<endl; 
    else 
    { 
        a[0]=r; 
        function(n,r); 
    } 
    return 0; 
}