46.全排列

给定一个不含重复数字的数组 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
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {

    // 用于存储当前路径的列表
    private List<Integer> path=new ArrayList<>();
    // 用于标记数字是否在当前路径中
    private boolean[] onPath;
    // 用于存储所有可能的排列结果的列表
    private final List<List<Integer>> ans = new ArrayList<>();

    // 主要方法，生成输入数组的所有排列组合
    public List<List<Integer>> permute(int[] nums) { 
        // 初始化标记数组，其长度为输入数组的长度
        onPath = new boolean[nums.length];
        // 开始深度优先搜索，初始状态为索引 0
        dfs(0,nums);
        return ans;
    }

    // 深度优先搜索方法
    private void dfs(int i,int [] nums) {
        // 如果路径长度等于输入数组的长度，说明找到了一个合法的排列
        if (i == nums.length) {
            // 将当前路径添加到结果列表中
            ans.add(new ArrayList<>(path));
            return;
        }

        // 遍历所有可能的数字
        for (int j = 0; j < nums.length; ++j) {
            // 如果数字不在当前路径中
            if (!onPath[j]) {
                // 将当前数字添加到路径中
                path.add(nums[j]);
                // 标记当前数字在路径中
                onPath[j] = true;
                // 继续搜索下一个位置
                dfs(i + 1,nums);
                // 回溯，移除当前数字和标记
                path.remove(path.size()-1);
                onPath[j] = false;
            }
        }
    }
}