给定一个不含重复数字的数组 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. 路径 (Path)：记录当前已经选择的数字（当前排列）。
2. 选择列表 (Choice)：当前还可以选择哪些数字？（排除掉已经存在于路径中的数字）。
3. 结束条件 (Base Case)：当“路径”的长度等于数组 nums 的长度时，说明所有的空位都填满了，这就是一个合法的全排列。将其加入结果集。

回溯的三部曲：

1. 做选择：从剩余的数字中选一个加入路径，并标记为已使用。
2. 递归：进入下一层决策树（填下一个空位）。
3. 撤销选择：递归返回后，将刚才加入路径的数字移除，并标记为未使用（只有撤销了，才能在当前空位尝试别的数字）。

Java实现

    public List<List<Integer>> permute(int[] nums) {
        // 最终结果集
        List<List<Integer>> res = new ArrayList<>();
        // 当前路径，当 path.size() == nums.length 时，说明找到了一个全排列
        List<Integer> path = new ArrayList<>();
        // used 数组用于记录当前路径中已经使用过的数字
        boolean[] used = new boolean[nums.length];

        if (nums == null || nums.length < 1){
            return res;
        }

        backTrack(nums, used, path, res);

        return res;
    }

    private void backTrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res){
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if(used[i] == true){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backTrack(nums, used, path, res);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }