C++刷题 全排列问题

题目描述

思路讲解

代码展示

#include <iostream>using namespace std;const int maxn = 11;//P为当前排列，hashTable记录整数x是否已经在P中
int n, P[maxn], hashTable[maxn] = {false};//当前处理排列的第index号位
void generateP(int index) {if (index == n + 1) { //递归边界，已经处理完排列的i~n位for (int i = 1; i <= n; i++) {printf("%d", P[i]); //输出当前排列}printf("\n");return;}for (int x = 1; x <= n; x++) { //枚举1~n，试图将x填入P[index]if (hashTable[x] == false) { //如果x不在P[0]~P[index - 1]中P[index] = x; //令P的第index位为x，即把x加入当前排列hashTable[x] = true; //记x已在P中generateP(index + 1); //处理排列的第index + 1号位hashTable[x] = false; // 已处理完P[index]为x的子问题，还原状态}}
}int main() {n = 3;  //欲输出1~3的全排列generateP(1); //从P[1]开始return 0;
}