用回溯 + DFS 查找全排列

题目链接-来源：力扣（LeetCode）

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

示例 1：

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

思路：

全排列的问题很直观，对于 nums 数组中的数字，我们可以用一个布尔型数组 visited[]将其标记为两类，一类是已经取到我们的结果集中的元素，另一类是尚未选择的元素。我们每次递归中，就按照一定的顺序（如，从后往前，或者从前往后，保证不遗漏即可），搜索 nums 中的尚未选择的元素，将其标为已选择（visited[i] 标记为 true），加入结果集，并在此基础上继续进行更深一层的 dfs。
回溯发生在深层 dfs 返回之后，我们要恢复现场，将相关变量恢复为好像没有发生过本次 dfs 一样，包括从结果集中删除选择的元素（对于本题，即为结果列表最后一个元素），修改 visited[i]。
递归中止的条件为结果集大小恰为 nums 的长度，表示我们已经得到了一组符合要求的结果，我们将其复制一份插入待返回的列表中，并跳出当前递归。
时间复杂度：O(n * n!)
空间复杂度：O(n)

实现：

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // Init
        List<List<Integer>> ret = new LinkedList<>();
        int len = nums.length;
        if (len == 0) {
            return ret;
        }
        List<Integer> ans = new ArrayList<>(len);
        boolean[] visited = new boolean[len];
        
        // Process
        dfs(nums, ret, ans, visited);
        return ret;
    }
    
    private void dfs(int[] nums, List<List<Integer>> ret, List<Integer> ans, boolean[] visited) {
        int len = nums.length;
        int size = ans.size();
        if (ans.size() == len) {
            ret.add(new ArrayList<Integer>(ans));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                ans.add(nums[i]);
                dfs(nums, ret, ans, visited);
                visited[i] = false;
                ans.remove(size);
            }
        }
    }
}