pascal问题:组合序列

Question

内容：

组合序列，组合一般是指从n（<=10)个不同元素中取r（<=n）个元素的不同组合的数目。按字典序
输入说明：

一行2个整数，如 3 2

输出说明：

每行一个组合序列，中间用空格隔开
输入样例：

若题目没有特别说明，则应该以多组测试数据方式读取，或者参考a001。3 2
输出样例 ：

1 2
1 3
2 3

请各位大大帮一下忙啦,我一看见这题目头就痛,请快快解答,越快越好!!!谢谢...
那个...您能给我源程序吗？我想要这个，听分析我还是有点像一头雾水。。。

Answer 1

首先对于样例，组合1 3，和组合3 1实质上是一样的，都是由1和3两个数构成，又因为一个数字只能用一次，所以我们可以人为规定选出的前一个数小于后一个数来避免重复。这样子你用一个dfs搜索即可。
dfs（i，j）表示当前要找第i个元素。其中已找到的第i-1个元素为j。那么有两种情况：
1：i=r+1：说明已经找到一种情况，输出。
2：i<>r+1：说明还没有完成组合，继续找。for k:=j+1 to n do dfs(i+1,k);
这样子就可以了。
可以证明这样子找到的一定字典序最小。 ……那我可敲源码啦，你到时候就看在我辛苦的份上选我的答案好了……程序保证给你对的。
Program Test;
var a:array[1..10]of longint;
n,r:longint;
procedure dfs(i,j:longint);
var k:longint;
begin
if i=r+1 then
begin
for k:=1 to r-1 do write(a[k],' ');
writeln(a[r]);
exit;
end;
for k:=j+1 to n do
begin
a[i]:=k;
dfs(i+1,k);
end;
end;
begin
readln(n,r);
dfs(1,0);
end.
程序各变量名含义见分析。