Problem: Permutations

Problem Statement

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

Approach: Backtracking Decision Tree

We build the permutation position by position. For each position, we have a choice of any remaining number.

1. Choice: Pick a number from the array that hasn't been used yet.
2. Constraint: Use a boolean[] used or contains() check to avoid duplicates.
3. Backtrack: After exploring the branch (recursion), remove the number from our current path to try a different choice.
4. Base Case: When the current path size equals the array size.

Java Implementation

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    if (tempList.size() == nums.length) {
        list.add(new ArrayList<>(tempList));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (tempList.contains(nums[i])) continue; // Element already used
        
        tempList.add(nums[i]); // Choose
        backtrack(list, tempList, nums); // Explore
        tempList.remove(tempList.size() - 1); // Un-choose
    }
}

Complexity Analysis

• Time Complexity: $O(n \times n!)$. There are $n!$ permutations, and we do $O(n)$ work to copy each one to the result list.
• Space Complexity: $O(n)$ for the recursion stack and the current path.

Interview Tips

• Mention the Factorial time complexity. This is expected when generating arrangements.
• Optimization: Use a boolean[] instead of contains() to reduce lookup from $O(n)$ to $O(1)$.