问题描述 N（N为偶数）个高矮不同的人排成两排照相，要求每一排都是从矮到高排列，而第二排每个人比第一排对应的人要高，列出所有可能的结果。 输入格式 第一行正整数N（0<N<100） 第二行第一个人的身高h1 第三行第二个人的身高h2 … 第N+1行第N个人的身高hN 输出格式 1.每种情况占据一行； 2.将第一排按照排队顺序输出身高，然后将第二排按照排队顺序输出身高； 3.身高之间加空格（第二排最后一人后面为换行符，无空格），两排之间不加换行符（第一排最后一人与第二排第一人之间为空格）。 4.最后统计所有情况数目并输出。 提示 1.使用<stdio.h>中的scanf，printf。它们比<iostream>中的cin, cout更快。 样例输入有两种排队方式，每种排队方式输出的顺序如图中红线所示： 其中，第一种排队方式对应输出如图所示，第二种同理。 2.每种情况输出完成后要换行。 3.在输出时，不同情况的输出先后顺序不影响答案的正确性。 思路提示 1.把最小身高放在第一排首位 2.选择一个合适的身高放在第二排首位 3.根据上述两个步骤进行递归操作 用C++11代码，最优算法，最低时间空间复杂度

以下是C++11代码，时间复杂度为O(N!)，空间复杂度为O(N)。由于是通过递归实现的，所以在N比较大的时候可能会出现栈溢出的情况。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 110;

int n;
int h[N];
vector<int> path;  // 用来存储每个人的排队顺序
int cnt;  // 记录总方案数

void dfs(int u, int t) {  // u表示当前已经选了多少人，t表示当前选的是第几排
    if (u == n) {  // 如果已经选完了所有人，就输出结果
        cnt++;
        for (int i = 0; i < n; i++) {  // 输出第一排
            if (i) cout << ' ';
            cout << h[path[i]];
        }
        cout << '\n';
        for (int i = 0; i < n; i++) {  // 输出第二排
            if (i) cout << ' ';
            cout << h[path[i + n]];
        }
        cout << '\n';
        return;
    }
    if (t == 1) {  // 如果当前选的是第一排，就从当前最小身高开始选
        int last = -1;  // 记录上一个选的人的身高
        for (int i = 0; i < n; i++) {
            if (h[i] > last) {  // 如果当前这个人比上一个人高
                path.push_back(i);  // 把这个人加入到排队顺序中
                last = h[i];
                dfs(u + 1, t);  // 递归下一位
                path.pop_back();  // 恢复现场
            }
        }
    } else {  // 如果当前选的是第二排，就从当前最小身高开始选
        int last = path[u - n - 1];  // 上一个选的人的身高
        for (int i = 0; i < n; i++) {
            if (h[i] > last) {  // 如果当前这个人比上一个人高
                path.push_back(i);  // 把这个人加入到排队顺序中
                dfs(u + 1, t);  // 递归下一位
                path.pop_back();  // 恢复现场
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);  // 先把身高排序
    dfs(0, 1);  // 从第一排开始选人
    cout << cnt << '\n';  // 输出方案数
    return 0;
}