求大神讲解一个比较难得C语言程序

Question

程序如下：
#include<stdio.h>
#include<string.h>
void printCombination(char*cs,int i,char*xs,int j,int m,int n)
{
if (j==n)
{
printf ("%s\n",xs);
return;
}

if (i+1>m)
return;

//当前字符不选中
printCombination(cs,i+1,xs,j,m,n);

//当前字符选中
xs[j]=cs[i];
printCombination(cs,i+1,xs,j+1,m,n);
}

#define M_MAX 128

int main()
{
char cs[M_MAX]={0};
char xs[M_MAX]={0};
int m;
int n;

printf ("请输入M个字符:");
scanf("%s",cs);
m=strlen(cs);

do
{
printf ("请输入N等于(N<=%d):",m);
scanf("%d",&n);
}
while(n>m);
printCombination(cs,0,xs,0,m,n);
}
每一步都帮忙讲解一下万分感谢

Answer 1

这个题的最终目的是输出长为 m 的字符串中任意 n 个字符的所有组合。如图：

题主提供的算法其实是帕斯卡法则的实现，即 

C ( n, k ) = C ( n - 1, k ) + C ( n - 1, k - 1 )

也就是说，要从 n 个东西中选出 k 个东西，首先要从 n 个东西中随便拿一个出来，这样就剩下 n - 1 个东西。这样，要选出 k 个东西，就有如下两种方法：

要么在剩下的 n - 1 个东西中选出 k - 1 个东西和刚才拿出的那一个配成 k 个，

要么干脆抛弃拿出来的那一个，直接从剩下的 n - 1 个东西中选出 k 个东西。

第一种方法共有 C ( n - 1, k - 1 ) 种拿法，而第二种方法共有 C ( n - 1, k ) 种拿法，二者相加就是全部的拿法 C ( n, k )。

理解了这个法则后，这段代码就比较容易看了。我把注释写在了下面：

#include <stdio.h>
#include <string.h>

#define M_MAX 128


int main() {

// 定义两个字符串，一个是用户输入的原始数据 cs，
// 另一个是将来要输出到屏幕上的字符组合 xs
char cs[M_MAX] = {0};
char xs[M_MAX] = {0};
int m;
int n;

void printCombination(char * cs, int i, char * xs, int j, int m, int n);

printf ("请输入M个字符: \n");

// 这里将用户输入的字符串储存到 cs 中。
scanf("%s", cs);

// 将字符串的长度赋给整数 m
m = strlen(cs);

// 这里是让用户输入想要的字符串组合的长度。比如我输入了
// 一个长度为 7 的字符串，然后在这儿输入了 4 ，那么就是
// 想让程序找出这 7 个字符中任意 4 个的组合。

// 这里的 do while 循环是为了让用户输入正确的数据。
// 如果用户输入的数字 n 大于字符串的长度 m，便是不正确的，
// 比如你不能从 8 个字符中找出 10 个字符的组合。不正确就会
// 一直循环提示用户输入，直到数字是合理的。
do {
printf ("请输入 N 等于(N <= %d)：", m);
scanf("%d", &n);
}
while (n > m);

// 利用 printCombination 函数打印出长度为 n 的所有组合。
printCombination(cs, 0, xs, 0, m, n);

return 0;

}

/**
 * 这个函数使用了递归，但是最好不要细抠每一次呼叫的细节，
 * 要从前面解释的宏观的算法的角度来看，否则很容易把自己绕进去。
 *
 * 这个函数实际上就是从长度为 m 的原始字符串 cs 中选出长度为 n
 * 的任意字符串。这和帕斯卡法则实质上是一样的。所以这个函数使用了
 * 帕斯卡法则的算法：
 * 首先将长为 m 的字符串 cs 中的一个字符取出，然后：
 * 方法 1. 从剩下的 m - 1 个字符中选出 n - 1 个，也就是
 *        printCombination(cs, i + 1, xs, j + 1, m, n);
 * 方法 2. 放弃取出来的字符，从剩下的 m - 1 个字符中直接挑出 n 个，也就是
 *        printCombination(cs, i + 1, xs, j, m, n);
 *
 *
 * 函数中每一个参数的含义：
 *
 * char * cs：用户输入的原始字符串。
 * int i：原始字符串的行进位置
 * char * xs：程序输出的字符的组合的字符串
 * int j：输出字符串的行进位置
 * int m：原始字符串的长度
 * int n：输出的字符串的长度
**/
void printCombination(char * cs, int i, char * xs, int j, int m, int n) {


// 这是递归终止的判断条件，如果 j 和 n 相等，说明 n 个被选出的字符的位置都被占了，
// 也就说明已经选出了 n 个字符，就可以打印出来 xs 并终止函数了。
if (j == n) {
printf ("%s\n", xs);
return;
}

// 这是另一个递归终止的判断条件，如果 i + 1 大于 m，也就是说已经试过了取出原始字符串的最后一个字符，
// 这样就没有再进行函数的余地了，于是函数终止。
if (i + 1 > m)
return;

// 方法 1
// 先将选出来的一个字符 cs[i] 加进结果的 xs[j] 中去，
xs[j] = cs[i];

// 然后把指示位置的 i 加一，跳过已经被选出的这个字符，这样就剩下 m - 1 个字符。
// 由于 xs[j] 已经被选出，所以 j + 1，定位到 xs 的下一
// 个空位去，也就是从剩下的 m - 1 个字符中再选出 n - 1 个字符。
printCombination(cs, i + 1, xs, j + 1, m, n);

// 方法 2
// 直接无视选出来的 cs[i] 字符，把指示位置的 i 加一跳过它，这样做后剩下 m - 1 个字符。
// 但由于无视了 cs[i]，使得 xs[j] 并没有被占用，所以这个位置依然是空的，
// 也就是说仍要选出 n 个字符。所以就从剩下的 m - 1 个字符中再选出 n 个字符。
printCombination(cs, i + 1, xs, j, m, n);

}