Permutations medium

Problem Statement

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

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1] Output: [[0,1],[1,0]]

Steps to Solve

The core idea is to use backtracking. We'll explore all possible arrangements by recursively placing each number in each possible position.

1. Base Case: If the current permutation has the same length as the input array, add it to the result list.

2. Recursive Step: For each element in the input array that hasn't been used yet:

   • Add the element to the current permutation.
   • Recursively call the function with the updated permutation and the remaining unused elements.
   • Remove the element from the current permutation (backtracking step) to explore other possibilities.

Detailed Explanation

Backtracking is a powerful algorithmic technique used to explore all possible solutions by systematically building up a solution and undoing choices (backtracking) when a solution is not found or a dead-end is reached.

In this problem, we start with an empty permutation. We iterate through the input array. For each number, we add it to our current permutation and recursively call the function to explore permutations with that number included. After the recursive call returns, we remove the number from the permutation. This "undoing" is crucial for exploring all possibilities because we need to reset the permutation to its previous state before considering the next number.

Code (Java)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPermutation = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // Track used numbers

        backtrack(nums, used, currentPermutation, result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> currentPermutation, List<List<Integer>> result) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation)); // Add a copy to avoid modification
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.add(nums[i]);
                backtrack(nums, used, currentPermutation, result);
                currentPermutation.remove(currentPermutation.size() - 1); // Backtrack
                used[i] = false;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n! * n). There are n! permutations, and adding each permutation to the result list takes O(n) time.

• Space Complexity: O(n). The space used is primarily due to the recursion stack and the currentPermutation list, both of which have a maximum depth of n. The result list also stores permutations, but its size is also proportional to n!. However, we usually focus on the space used during the recursive calls (the stack space), which is O(n).