class Solution {
    public List<List<Integer>> permute(int[] a) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(-1, a, result, path);
        return result;
    }
    private void dfs(int index, int[] a, List<List<Integer>> result, List<Integer> path){
        if(index != -1){
            path.add(a[index]);
        }

        if(index == a.length - 1){
            result.add(new ArrayList<>(path));
        }

        for(int i = index + 1; i< a.length; i++){
            swap(index + 1, i, a);
            dfs(index + 1, a, result, path);
            swap(index + 1, i, a);
        }

        if(index != -1){
            path.remove(path.size() - 1);
        }
    }
    private void swap(int i, int j, int[] a){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}