老子的全排列呢

链接

本题要求输出1-8的全排列,手动输入完全不现实,本题可采用回溯法,本质还是递归 不妨以1-3为例,先构建一个数组{1,2,3}

要实现全排列,就是给数组的每个元素排序 我们可用一个标记数组used{0,0,0},和用于输出的数组path 进入循环

1.used={1,0,0} path={1}第一层就放入第一个数接着进入第二层

2.used=(1,1,0)path={1,2}

3used={1,1,1}path={1,2,3}此时达到输出要求,可以加一个条件,即path. size()=3时,输出

输出完成一步一步退出循环,回到第二层

2.used={1,0,1}path={1,3}

3.used={1,1,1}path={1,3,2}输出

退回第一层

1.used={0,1,0}path={2}如此进行下去

其实就是控制used为真值的位置来决定path先填入的元素

代码实现

#include<iostream>
#include<vector>
using namespace std;
void f(vector<int>& nums, vector<int>& path, vector<bool>& used) {
 	if (path.size() == nums.size()) {
 		for (int num : path) {
 			cout << num << " ";
 		}
 		cout << endl;
 		return;
 	}
 	for (int i = 0;i < nums.size();i++) {
 		if (!used[i]) {
 			used[i] = 1;
 			path.push_back(nums[i]);
 			f(nums, path, used);
 			used[i] = 0;
 			path.pop_back();
 		}
 	}
}
int main() {
 	vector<int>nums = { 1,2,3,4,5,6,7,8 };
 	vector<int>path;
 	vector<bool>used(8, false);
 	f(nums, path, used);
 	return 0;
}

时间复杂度:O(n*n!)

空间复杂度:O(n).