AcWing 823. 排列
原题链接
困难
C++ 代码
#include <iostream>
using namespace std;
int n;
void dfs(int u, int nums[], bool state[])
{
//结束条件
if (u > n){
for (int i = 1; i <= n; i ++)
cout << nums[i] << ' ';
cout << endl;
}
//填当前位置数。
//先判断有没有填过确定位置,填当前循环情况的可能数,mark该数字用过,接着dfs下一层
//dfs深度优先,一个分支结束后返回,需将该数重新mark为未填,才能循环到下一种情况
else {
for (int i = 1; i <= n; i ++)
{
if (!state[i])
{
nums[u] = i;
state[i] = true; // mark为用过该数字了
dfs(u + 1, nums, state);
state[i] = false; // 为下一次循环做准备,退回到上一层,重新标记未选择的数
}
}
}
}
int main(){
cin >> n;
int nums[10];
bool state[10] = {0}; //该位置未填过为0, 填过为1
dfs(1, nums, state);
return 0;
}