分治法

#include<iostream>
#include<math.h>
using namespace std;
void DE(int *num,int n,int m) {
	if (n == m) {
		for (int i = 0; i <= m; i++) {
			cout << num[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = n; i <= m; i++) {
		swap(num[n],num[i]);
		DE(num,n + 1, m);
		swap(num[n],num[i]);
	}
}
int main() {
	int n;
	while (cin>>n) {
		int* num = new int[n];
		for (int i = 0; i < n; i++) {
			num[i] = i + 1;
		}
		DE(num, 0, n-1);
		delete[] num;
	}

}

回溯法

#include<iostream>
using namespace std;
int num[8];
bool flag[8]{};
void DFS(int step,int n) {
	if (step == n) {
		for (int i = 0; i < n; i++) {
			cout << num[i]<<" ";
		}
		cout << endl;
		return;
	}

	for (int i = 0; i < n; i++) {
		if (flag[i] == 0) {
			flag[i] = 1;
			num[step] = i+1;
			DFS(step+1,n);
			flag[i] = 0;
		}
	}
}
int main() {
	int n;
	while (cin >> n) {
		if (n == 0)break;
		DFS(0, n);
	}
}