一个dfs的起点放在另一个dfs的终点, 可以配出两组dfs序列自由组合的所有情况;
有点像1~n的排列和1~m的排列的所有笛卡尔积;

#include <iostream>

using namespace std;

const int N = 20;

int n, m;
bool st[N];
int path[N];

void dfs2(int u)
{
    if(u == m + n)
    {
        for(int i = 0;i < u;i ++) cout << path[i] << ' ';
        cout << endl;
        return ;
    }

    for(int i = 1;i <= m;i ++)
        if(st[i])
        {
            path[u] = i;
            st[i] = false;
            dfs2(u + 1);
            st[i] = true;
        }
}

void dfs1(int u)
{
    if(u == n) 
    {
        dfs2(u);
        return ;    
    }

    for(int i = 1;i <= n;i ++)
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs1(u + 1);
            st[i] = false;
        }
}

int main()
{
    cin >> n >> m;

    dfs1(0);

    return 0;
}

一个dfs的起点放在另一个dfs枚举的过程中, 枚举一个数组中的两组不同排列的组合;

#include <iostream>

using namespace std;

const int N = 20;

int n;
bool st[N];
int path[N];

void dfs2(int u, int v)
{
    if(u == n)
    {
        for(int i = 0;i < v;i ++) cout << path[i] << ' ' ;
        cout << endl;
        for(int i = v;i < n;i ++) cout << path[i] << ' ' ;
        cout << endl;
        cout << endl;
        return ;
    }

    for(int i = 1;i <= n;i ++)
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs2(u + 1, v);
            st[i] = false;
        }
}

void dfs1(int u)
{
    if(u > n) return ;
    dfs2(u, u);

    for(int i = 1;i <= n;i ++)
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs1(u + 1);
            st[i] = false;
        }
}

int main()
{
    cin >> n;

    dfs1(0);

    return 0;
}