class Solution {
    // 回溯算法，用一个boolean类型的数组标记已经使用过的数字
    // 回溯三要素：回溯函数的参数和返回类型、回溯的终止条件、回溯搜索的遍历过程
    // 全排列：非常经典的回溯算法，回溯算法的本质上遍历所有的和能效
    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new LinkedList();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums,used);
        return res;

    }
    public void backtracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == true) continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums,used);
            path.remove(path.size() - 1); // 后两步是在回溯，表明当前前缀数字的所有可能性都已经遍历完
            used[i] = false; 
        }
    }
    // public void backtracking(int[] nums, boolean[] used){
    //     if(path.size() == nums.length){
    //         res.add(new ArrayList(path)); // 需要注意：这里是new ArrayList(path) ,不是直接path，因为path是一直在变化的
    //         return;
    //     }
    //     for(int i = 0; i < nums.length ; i++){
    //         if(used[i] == true)continue;
    //         path.add(nums[i]);
    //         used[i] = true;
    //         backtracking(nums,used);
    //         path.removeLast();
    //         used[i] = false;
    //     }
    // }
}