从M个数中选N个

  从M个数中取N个，打印所有的方式。在好多地方看到这个题作为笔试/面试题。

 

  挺简单的。

 

#include <iostream>

using namespace std;

#define M 5
#define N 3
int source[M] = {0};
int dest[N] = {0};
int s_index = 0;
int d_index = 0;

void display(int source[], int s_index, int dest[], int d_index, int num)
{
    // 如果在source[]中剩下的数正好是N个，则打印并返回；包括已经放入dest[]中的，现在已经不能再做选择，否则剩余的数不够N

    if(s_index + num == M)
    {
        for(int i=0; i<d_index; i++)
        {
            cout << dest[i] << " ";
        }
        for(int j=s_index; j<M; j++)
        {
            cout << source[j] << " ";
        }
        cout << endl;
        return;
    }

    // 如果最后只需从source[]中选1个，则遍历source[]剩下的数

    if(num == 1)
    {
        for(int i=s_index; i<M; i++)
        {
            for(int j=0; j<d_index; j++)
            {
                cout << dest[j] << " ";
            }
            cout << source[i] << endl;
        }
        return;
    }

    display(source, s_index+1, dest, d_index, num); // source[s_index]没选中，则在剩下的source[]中选num个

    dest[d_index++] = source[s_index++]; // 把选中的数放进dest[]中

    display(source, s_index, dest, d_index, num-1); // source[s_index]选中，则在剩下的source中继续选num-1个

}

void main()
{
    for(int i=0; i<M; i++)
    {
        source[i] = i + 1;
    }
    display(source, 0, dest, 0, N);
}