46. 全排列

1. 题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

2. 思路

  • 已知题目要求获取输入数组的全排列结果集，同时nums[i]的取值为[-10, 10]这个区间
  • 初始化结果集result与访问标记值为-11，同时采用通用回溯算法定义dfs函数，回溯算法的模板为以下：
1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
  • 本题中，回溯算法的参数为nums数组与list临时结果集，其中终止条件为当list结果子集长度与nums数组长度一致时，将list结果子集写入result中
  • 处理节点的过程中，需要判断哪些元素已经被使用，因此可以利用nums[i]取值区间，将已访问过的元素赋值为-11，并且在当遇到已访问的元素时，将不对元素进行操作
  • 一层回溯完成后，需要将已访问元素的标记进行还原，同时对list结果子集的结尾元素进行删除（撤销操作），完成整体回溯后，即可返回result结果集

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private static final int VISITED = -11;

    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, new ArrayList<Integer>());
        return result;
    }

    private void dfs(int[] nums, List<Integer> list) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (var i = 0; i < nums.length; ++i) {
            var num = nums[i];
            if (num == VISITED) {
                continue;
            }
            
            nums[i] = VISITED;
            list.add(num);
            dfs(nums, list);
            list.remove(list.size() - 1);
            nums[i] = num;
        }
    }

}

4. 复杂度

  • 时间复杂度：O(n * n!)，其中n为序列的长度
  • 空间复杂度：O(n)，其中n为序列长度，因为除了答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所需要的额外空间取决于递归的深度，因此调用深度为O(n)

image-20230823005517027