一道算法题。
给定一个正整数 n (2 < n < 7)，给出所有由 1~n 组成的 n 位全排列（即 n! 个）。
输入样例：
3
输出样例：
123 132 213 231 312 321
输出结果按从小到大排序。
思路就是递归暴力枚举（回溯）。。。这样思考或许有助于写出递归方法：假设枚举值可以这样表示 $xm_i...m_{1}$，这里 x 表示是最高位，其他位依次递减为 $m_i (i = n - 1, n - 2, ..., 1)$，注意到每一位上都可以取 $1~n$ 的值，然后考虑到对于每一个取值情况，问题可以用子问题表示，然后只要求出所有子问题即可得到问题的解，所以我们划分子问题为 $m_{i}, m_{i}m_{i-1}, ..., m_{i}m_{i-1}...m_2, m_{i}m_{i-1}...m_2m_1$。
我的解决方案：
#include <iostream>
#include <cmath>
#include <functional>
#include <algorithm>
#include <vector>
const int N = 7;
int f[] = { 0, 0, 1, 2, 6, 24, 120, 720 };
int c = 0;
inline int sum(std::vector<int> a, int n)
{
int rt = 0;
for (int i = 0; i < n; i++) rt += a[i];
return rt;
}
void rec(int n, int m, int k, std::vector<int>& s, std::vector<int> it, int u)
{
if (n == 0) return;
if (it[m - 1] == 0)
{
k = k * 10 + m;
it[m - 1] = 1;
}
else return;
if (sum(it, u) == u)
{
c++;
s.push_back(k);
if (c == f[u])
{
c = 0; for (int j = 0; j < u; j++) it[j] = 0;
rec(n - 1, n - 1, 0, s, it, u);
}
return;
}
for (int i = u; i > 0; i--) rec(n, i, k, s, it, u);
}
int main()
{
std::vector<int> s;
std::vector<int> it(N);
int n = 7;
rec(n, n, 0, s, it, n);
std::for_each(s.rbegin(), s.rend(), [](const int& i) { std::cout << i << " "; });
return 0;
}
python 解决方案：
p = {2: 1, 3: 2, 4: 6, 5: 24, 6: 120, 7: 720}
def rec(n, m, k, s, it, u):
global c
if n == 0:
return
if it[m - 1] == 0:
k = k*10 + m
it[m - 1] = 1
else:
return
if sum(it) == u:
s += [k]
c += 1
return
for i in range(u, 0, -1):
rec(n, i, k, s, it.copy(), u)
if c != p[u]:
return
c = 0
for _ in range(u):
it[_] = 0
rec(n - 1, n - 1, 0, s, it.copy(), u)
n = int(input())
it = [0] * n
s = []
c = 0
rec(n, n, 0, s, it, n)
print(s[::-1])
原文：https://www.cnblogs.com/darkchii/p/12735563.html