import java.util.*;

public class Solution {
    private static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); 
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        //注意回溯法的通用解法
        //引入队列
        Deque<Integer> deque = new ArrayDeque<>();
        if( num.length == 0){
            return result;
        }
        //辅助数组,标识是否使用过
        boolean[] used = new boolean[num.length];
        backTracking(num,deque,used);
        return result;

    }

    public static void backTracking(int[] num,Deque<Integer> list,boolean[] used){
        if(list.size() == num.length){
            result.add(new ArrayList<>(list));
            return;
        }
        //注意全排列这里的起点是0,但是组合是startIndex
        for(int i=0;i<num.length;i++){
            if(used[i] == true){
                continue;
            }
            used[i] = true;
            list.addLast(num[i]);
            backTracking(num,list,used);
            //回溯
            used[i] = false;
            list.removeLast();

        }
    }

}

解题思想:dfs标准套路,回朔逐个枚举,主要是确认需要枚举的下一个元素。