leetcode-46：全排列

问题

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

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

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

示例 3：
输入：nums = [1]
输出：[[1]]

思路

我以[1,2,3]为例，抽象成树形结构如下：

回溯三部曲

• 递归函数参数
  • 首先排列是有序的，也就是说**[1,2]**和**[2,1]**是两个集合，这和之前分析的子集以及组合所不同的地方，可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了
  • 但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示

List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public void backtracking (int[] nums, boolean[] used)

• 递归终止条件
  • 可以看出叶子节点，就是收割结果的地方
  • 那么什么时候，算是到达叶子节点呢？
    • 当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点 ```java if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }

不能是result.add(path); 在 Java 中，参数传递是值传递，对象类型变量在传参的过程中，复制的是变量的地址。 这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到多个空的列表对象 解决的方法很简单，在 res.add(path); 这里做一次拷贝即可

- **单层搜索的逻辑**
   - 这里和[组合问题](https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485253&idx=1&sn=8332edaabc9bf43e45835bce7964ce88&scene=21#wechat_redirect)、[切割问题](https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485372&idx=1&sn=29cc3421fb742faa57824b9a626342ad&scene=21#wechat_redirect)和[子集问题](https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485402&idx=1&sn=6963af3e2aa8d58e41b71d73d53ea8f6&scene=21#wechat_redirect)最大的不同就是`for`循环里不用`startIndex`了
   - 因为排列问题，每次都要从头开始搜索，例如元素`1`在`[1,2]`中已经使用过了，但是在`[2,1]`中还要再使用一次`1`
   - **而**`**used**`**数组，其实就是记录此时**`**path**`**里都有哪些元素使用了，一个排列里一个元素只能使用一次**
```java
for (int i = 0; i < nums.length; i++) {
    if (used[i] == true) 
        continue; // path里已经收录的元素，直接跳过
    used[i] = true;
    path.add(nums[i]);
    backtracking(nums, used);
    path.remove(path.size() - 1);
    used[i] = false;
}

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public void backtracking (int[] nums, boolean[] used){
        // 此时说明找到了一组
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == true) 
                continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums, used);
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> list = solution.permute(nums);
        System.out.println(list);
    }
}