class Solution {
    List<List<Integer>> res = new ArrayList();
    List<Integer> ans = new ArrayList();
    boolean[] st;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        st = new boolean[n];
        dfs(nums, 0);

        return res;
    }

    public void dfs(int[] nums, int u){
        if(u == nums.length){
            res.add(new ArrayList(ans));
            return;
        }

        for(int i = 0; i < nums.length; i ++ ){
            if(st[i] != true){
                st[i] = true;
                ans.add(nums[i]);
                dfs(nums, u + 1);
                ans.remove(ans.size() - 1);
                st[i] = false;
            }
        }
    }
}