P1157 组合的输出——题解

解题思路

递归确定组合的第 dep 个数字。为了保持递增，当前数字只能大于上一个数字；为了保证剩余位置还能填满，上界可缩小为 n-(r-dep)。按从小到大的顺序枚举即可得到字典序。

正确性说明

每条完整路径严格递增，所以对应唯一组合。任意大小为 $r$ 的组合按升序排列后，都满足递归的选择范围，会被唯一访问一次。

复杂度分析

设组合数为 $C(n,r)$，时间复杂度 $O(rC(n,r))$，递归空间 $O(r)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,r,a[25];
void dfs(int dep,int last){
    if(dep>r){
        for(int i=1;i<=r;i++) cout<<setw(3)<<a[i];
        cout<<'\n'; return;
    }
    for(int x=last+1;x<=n-(r-dep);x++){
        a[dep]=x; dfs(dep+1,x);
    }
}
int main(){cin>>n>>r;dfs(1,0);return 0;}

#include <bits/stdc++.h> using namespace std; int n,r,a[25]; void dfs(int dep,int last){ if(dep>r){ for(int i=1;i<=r;i++) cout<<setw(3)<<a[i]; cout<<'\n'; return; } for(int x=last+1;x<=n-(r-dep);x++){ a[dep]=x; dfs(dep+1,x); } } int main(){cin>>n>>r;dfs(1,0);return 0;}