[C++] 降序优先的全排列

共计 902 个字符，预计需要花费 3 分钟才能阅读完成。

题目

给定 n 个互不相同的正整数，这些数可能是乱序的。请编写一个程序，输出这些数字的所有可能全排列，但要求先输出较大的数字。

输入描述

第一行包含一个正整数 n（1 ≤ n ≤ 9）。
第二行包含 n 个互不相同的正整数，用空格分隔。

输出描述

输出所有可能的全排列，每种排列占一行。

样例

输入

3
9 7 12

输出

12 9 7
12 7 9
9 12 7
9 7 12
7 12 9
7 9 12

题解

#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void search(vector<long long> rest, vector<long long> cover){if(rest.empty()){for(long long number : cover){cout << number << " ";}
        cout << endl;
        return;
    }
    for(int i=0;i<rest.size();i++){vector<long long> newRest(rest.begin(), rest.begin()+i);
        newRest.insert(newRest.end(), rest.begin()+i+1, rest.end());
        vector<long long> newCover(cover.begin(), cover.end());
        newCover.insert(newCover.end(), rest[i]);
        search(newRest, newCover);
    }
}

bool cmp(long long a, long long b){return a>b;}

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<long long> l(n);
    for(int i=0;i<n;i++) cin >> l[i];

    sort(l.begin(),l.end(),cmp);

    search(l, {});

    return 0;
}

简单深度优先搜索，主要难点是传递上下文。