class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;

        dfs(nums, new ArrayList<>(), ans);

        return ans;
    }

    private void dfs(int[] nums, List<Integer> path, List<List<Integer>> ans){
        if (path.size() == nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (nums[i] == Integer.MAX_VALUE) continue;
            int old = nums[i];
            path.add(nums[i]);
            nums[i] = Integer.MAX_VALUE;
            dfs(nums, path, ans);
            path.remove(path.size() - 1);
            nums[i] = old;
        }
    }
}