class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        helper(nums, 0, ans, new ArrayList<Integer>());
        return ans;
    }
    private void helper(int[] nums, int idx, List<List<Integer>> ans, ArrayList<Integer> path){
        if(idx == nums.length) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = idx; i < nums.length; i++){
            path.add(nums[i]);
            swap(nums, i, idx);
            helper(nums, idx+1, ans, path);
            swap(nums, i, idx);
            path.remove(path.size()-1);
        }
        return;
    }
    
    private void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}