class Solution {
    List<List<Integer>> solution = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> thisRun = new ArrayList<>();
        permuteRec(nums, 0, thisRun, new int[nums.length]);
        return solution;
    }
    
    public void permuteRec(int[] nums, int index, List<Integer> run, int[] visited) {
        if(index >= nums.length) {
            solution.add(run);
            return;
        }
        
        for(int i=0; i<nums.length; i++) {
            if(visited[i] == 0) {
                List<Integer> thisRun = new ArrayList<>();
                thisRun.addAll(run);
                thisRun.add(nums[i]);
                visited[i] = 1;
                permuteRec(nums, index+1, thisRun, visited);
                visited[i] = 0;
            }
        }
    }
}