给出 n 互不相同的数，输出它们的 n！个排列。每组数据第一行为正整数 。第二行 n 个互不相同的不大于 1000 的正整数。按字典序从小到大输出这组数的全排列。两个排列在字典序的大小关系指，从第一个位置开始比较，遇到的第一个不相同的数时，较小的那个所在的排列字典序更小。使用回溯的方法，时间限制为一秒。

题目描述

给出 n 互不相同的数，输出它们的 n！个排列。每组数据第一行为正整数 n。第二行 n 个互不相同的不大于 1000 的正整数。按字典序从小到大输出这组数的全排列。两个排列在字典序的大小关系指，从第一个位置开始比较，遇到的第一个不相同的数时，较小的那个所在的排列字典序更小。

输入格式

第一行为正整数 n。

第二行 n 个互不相同的不大于 1000 的正整数。

输出格式

按字典序从小到大输出这组数的全排列，每个排列占一行。

输入样例

3
1 2 3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

提示

数据范围：1≤n≤9

算法1

(回溯) $O(n!)$

1.回溯模板
2.使用used[]标记该数是否使用过，每次选择一个未使用的数
3.如果选择数的个数等于n，就输出结果。

时间复杂度

$O(n!)$

C++ 代码

相关问题

有 n(1\leq n < 10)n(1≤n<10) 个升序排序的互不相同的数 a_ia i ​ ，求出：从中任取 r(0<r \le n)r(0<r≤n) 个数的所有组合情况。 输入格式 第一行输入 nn、rr。 第二行 nn 个正整数 a_i(1\leq a_i \leq 100)a i ​ (1≤a i ​ ≤100)。 输出格式 按特定顺序输出所有组合。 特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。 格式说明 输出时每行末尾的多余空格，不影响答案正确性 输入、输出要求 要求使用「文件输入、输出」的方式解题，输入文件为 combine.in，输出文件为 combine.out C++代码

你可以使用递归来解决这个问题。假设你已经求出了取 r-1 个数的所有组合，那么对于每一个组合，你可以在它的末尾加上一个比当前组合中所有数都大的数，这样就可以得到取 r 个数的所有组合。

你可以使用一个数组来存储当前组合，然后使用一个变量来记录当前组合中的数的个数。每次递归时，你可以先将当前组合的数的个数加 1，然后再将一个比当前组合中所有数都大的数加入当前组合。

当递归到 r 个数时，你就可以将当前组合输出到文件中，然后再继续递归。

代码如下：

void combine(int n, int r, int* a, int* comb, int comb_size) {
  if (comb_size == r) {
    // 将当前组合输出到文件中
    return;
  }
  // 从大到小枚举比当前组合中所有数都大的数
  for (int i = n - 1; i >= 0; i--) {
    comb[comb_size] = a[i];
    // 递归求解
    combine(i, r, a, comb, comb_size + 1);
  }
}

你还需要自行实现文件输入、输出的部分。