递归实现排列型枚举

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int path[10];
bool st[10];
void dfs(int u)
{
    if(u >= n)
    {
        for(int i = 0; i < n; i ++)
            printf("%d ", path[i]);
        puts("");
        return;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(st[i] == 0)
        {
            st[i] = 1;
            path[u] = i;
            dfs(u + 1);
            st[i] = 0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

递归实现组合型枚举

分析

    不同于排列型枚举，组合型枚举不考虑元素的排列顺序，如1 2 3和1 3 2是两种不同
的排列，但却是两种相同的组合方式，为了避免出现这种情况，我们要求得到的每一个组
合中的元素，在原数组中的下标是递增或是递减的。

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
int path[30];
//u表示正在考虑第u个位置应该放哪一个元素（记该元素为a）
//start表示下一位置要放的元素必须是元素a在原序列位置后面的元素
//start是组合型枚举的精髓，以保证得到的每一个组合中的元素，在
//原数组中的下标是递增或是递减的
void dfs(int u, int start)
{
    if(u > m)
    {
        for(int i = 1; i <= m; i ++)
            printf("%d ", path[i]);
        puts("");
        return;
    }
    for(int i = start; i <= n; i ++)
    {
        path[u] = i;
        dfs(u + 1, i + 1);
    }
}
int main()
{
    cin >> n >> m;
    dfs(1, 1);
    return 0;
}