思路

利用回溯排列

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]]

复杂度分析

回溯算法由于其遍历的特点，时间复杂度一般都比较高，有些问题分析起来很复杂。一些回溯算法解决的问题，剪枝剪得好的话，复杂度会降得很低，因此分析最坏时间复杂度的意义也不是很大。但还是视情况而定。

时间复杂度： $O(n*n!)$
空间复杂度 $O(n*n!)$

时间复杂度分析

在第 1 层，结点个数为 N个数选 1 个的排列
在第 2 层，结点个数为 N个数选 2 个的排列
所以：非叶子节点个数
$1+\sideset{}{^1_{n}}A +\sideset{}{^2_{n}}A +\sideset{}{^3_{n}}A +... +\sideset{}{^{n-1}_{n}}A$
= $1+n!/(n-1)! +n!/(n-2)! +n!/(n-3)! +... +n!$