Permutations

Description

Permutations
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]]

Example 3:
Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Brute Force Approach: Standard Backtracking with Visited Array

Intuition

Build permutations element by element. To avoid picking the same element twice in a single permutation, maintain a boolean visited array to keep track of which numbers are currently in use.

import java.util.*;
 
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(nums, visited, new ArrayList<>(), result);
        return result;
    }
 
    private void backtrack(int[] nums, boolean[] visited, List<Integer> current, List<List<Integer>> result) {
        // Base case: permutation complete
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
 
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                // 1. CHOOSE
                visited[i] = true;
                current.add(nums[i]);
 
                // 2. EXPLORE
                backtrack(nums, visited, current, result);
 
                // 3. UN-CHOOSE (Backtrack)
                current.remove(current.size() - 1);
                visited[i] = false;
            }
        }
    }
}
 

Complexity

• Time Complexity: $O(n!\cdot n)$ — There are $n!$ total permutations, and copying each permutation takes $O(n)$ time.
• Space Complexity: $O(n)$ — Auxiliary space for the visited array, temporary current list, and recursion stack.

---

Most Optimized Solution: In-Place Swapping Backtracking

Intuition

Instead of using an extra visited array and temporary list, generate permutations in-place by swapping elements directly in the array:

1. Maintain start representing the current index to fill.
2. Iterate i from start to nums.length - 1.
3. Swap nums[start] with nums[i] (placing nums[i] at the current position).
4. Recurse for start + 1.
5. Swap nums[start] back with nums[i] to restore the original array state for the next iteration (Backtrack).

nums = [1, 2, 3], start = 0
 
               swap(0,0)                swap(0,1)                swap(0,2)
               [1, 2, 3]                [2, 1, 3]                [3, 2, 1]
              /         \              /         \              /         \
         swap(1,1)   swap(1,2)    swap(1,1)   swap(1,2)    swap(1,1)   swap(1,2)
         [1, 2, 3]   [1, 3, 2]    [2, 1, 3]   [2, 3, 1]    [3, 2, 1]   [3, 1, 2]
 

import java.util.*;
 
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, nums, result);
        return result;
    }
 
    private void backtrack(int start, int[] nums, List<List<Integer>> result) {
        // Base case: filled all positions
        if (start == nums.length) {
            List<Integer> current = new ArrayList<>();
            for (int num : nums) {
                current.add(num);
            }
            result.add(current);
            return;
        }
 
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);              // 1. CHOOSE (Swap into current spot)
            backtrack(start + 1, nums, result); // 2. EXPLORE
            swap(nums, start, i);              // 3. UN-CHOOSE (Swap back)
        }
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
 

Complexity

• Time Complexity: $O(n!\cdot n)$ — $n!$ permutations, spending $O(n)$ to copy elements into the result list.
• Space Complexity: $O(n)$ — Auxiliary space reduced by eliminating the visited array; uses only $O(n)$ recursion stack space.

---

Easy Memory Rule

“For Permutations without extra space: Loop i from start to end $\to$ Swap start and i $\to$ Recurse on start + 1 $\to$ Swap back.”