C++ 全排列算法优化：效率提升与代码改进

#include<bits/stdc++.h> using namespace std;

void dfs(vector& a, vector& b, int x){ if(x == a.size()){ for(int i = 0; i < a.size(); i++){ cout << a[i] << ' '; } cout << endl; return; } for(int i = 1; i <= a.size(); i++){ if(b[i] == 0){ b[i] = 1; a[x] = i; dfs(a, b, x + 1); b[i] = 0; } } }

int main(){ int n; cin >> n; vector a(n); vector b(n + 1); dfs(a, b, 0); return 0; }

优化说明：

1. 移出循环体代码： 在递归函数中，将循环体内的代码 b[i]=1; a[x]=i; 和 b[i]=0; 移到循环外部，避免重复计算，提高效率。

2. 引用传递数组： 使用引用传递 a 和 b 数组，避免数组复制带来的额外开销。

3. 添加剪枝操作： 在循环中，使用 b[i] == 0 条件判断是否已经取过某个数，如果已经取过，则直接跳过，避免重复计算。

代码改进后的优势：

• 减少循环次数，提高算法效率
• 避免数组复制，减少内存开销
• 添加剪枝操作，减少不必要的计算

示例：

假设输入 n = 3，则输出如下：

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