46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

DFS, Backtrack

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums,0,res);
        return res;
    }
    
    // depth represents the index in nums which will be swapped with the following integers
    private void dfs(int[] nums, int depth, List<List<Integer>> list){
        if (depth == nums.length-1) {
            // to be implemented
            List<Integer> ans = new ArrayList<>();
            for (int num : nums){
                ans.add(num);
            }
            list.add(ans);
            return;
        }
        
        for (int i=depth; i<nums.length;i++){
            swap(nums, depth, i);
            dfs(nums, depth+1, list);
            swap(nums, i, depth);
        }     
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[j];
        nums[j]=nums[i];
        nums[i]=temp;
    }
}