[toc]
题目：https://leetcode-cn.com/problems/permutations/
思路
利用回溯排列
image.png
代码
class Solution {
List<List<int>> res; //最后的结果
List<bool> used; //已经用到的
List<int> path; //记录成功的一条
List<List<int>> permute(List<int> nums) {
int len = nums.length;
res = new List();
if (len == 0) {
return res;
}
used = List(len);
path = List<int>();
dfs(nums, 0);
return res;
}
void dfs(
List<int> nums,
int depth,
) {
int len = nums.length;
if (depth == len) {
res.add(List.from(path)); //因为是指针传递，所以复制一份出来
return;
}
for (int i = 0; i < len; i++) {
if (used[i] != true) {
path.add(nums[i]);
used[i] = true;
// print('递归之前 =>$path');
dfs(nums, depth + 1);
//回溯 回复现场
used[i] = false;
path.removeLast();
// print('递归之后 i=$i =>$path');
}
}
}
}
验证
main(List<String> args) {
List<int> nums = [1, 2, 3];
Solution s = Solution();
print(s.permute(nums));
}
结果
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
复杂度分析
回溯算法由于其遍历的特点，时间复杂度一般都比较高，有些问题分析起来很复杂。一些回溯算法解决的问题，剪枝剪得好的话，复杂度会降得很低，因此分析最坏时间复杂度的意义也不是很大。但还是视情况而定。
- 时间复杂度：
- 空间复杂度
时间复杂度分析
- 在第 1 层，结点个数为 N个数选 1 个的排列
- 在第 2 层，结点个数为 N个数选 2 个的排列
所以：非叶子节点个数
=
因为
=
<= <2N!
将常规系数2视为1，每个内部循环N次，故非叶子时间复杂度为
