1. Problem Overview

The “Permutations” problem is a backtracking problem where we are asked to generate all possible arrangements (permutations) of a given array of distinct integers.

Problem Statement (LeetCode 46)

Given an array nums of distinct integers, return all the possible permutations.
You may 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]]

---

2. Understanding the Problem

If we have n distinct elements, there are n! (n factorial) possible permutations.
For example:

• For [1,2,3], there are 3! = 6 permutations.
• For [1,2,3,4], there are 4! = 24 permutations.

The task is to generate all these permutations programmatically.

---

3. Key Concept: Backtracking

This problem is a classic use case for backtracking.

What is Backtracking?

Backtracking is a recursive approach where we:

1. Build a partial solution step-by-step.
2. Explore all possible choices.
3. When a choice leads to a complete solution, we record it.
4. When a choice doesn’t work, we backtrack — i.e., undo the last step and try another.

It’s essentially a depth-first search (DFS) through all possible arrangements.

---

4. Step-by-Step Approach

Let’s break down the logic in detail.

Step 1: Choose an element

Pick one number from the array.

Step 2: Mark it as used

We should ensure we don’t use the same number twice in a permutation.

Step 3: Recursively build the permutation

Continue choosing from remaining unused numbers.

Step 4: Backtrack

After exploring one branch, undo the last choice and explore the next possibility.

---

Example Walkthrough (nums = [1, 2, 3])

Let’s visualize the recursive process:

Start: []
Pick 1 → [1]
   Pick 2 → [1,2]
      Pick 3 → [1,2,3] → Add to result
   Backtrack → [1,2]
   Pick 3 → [1,3]
      Pick 2 → [1,3,2] → Add to result
Backtrack → [1]
Pick 2 → [2]
   Pick 1 → [2,1]
      Pick 3 → [2,1,3] → Add to result
   Pick 3 → [2,3]
      Pick 1 → [2,3,1] → Add to result
Backtrack → [2]
Pick 3 → [3]
   Pick 1 → [3,1]
      Pick 2 → [3,1,2] → Add to result
   Pick 2 → [3,2]
      Pick 1 → [3,2,1] → Add to result

Output:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

---

5. Java Implementation (Backtracking Approach)

import java.util.*;

public class Permutations {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // Track used elements
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
        // Base case: when current permutation is complete
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // Add a copy
            return;
        }

        // Try each unused element
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // Choose
                used[i] = true;
                current.add(nums[i]);

                // Explore
                backtrack(nums, current, used, result);

                // Undo (backtrack)
                used[i] = false;
                current.remove(current.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Permutations obj = new Permutations();
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = obj.permute(nums);

        System.out.println("All Permutations:");
        for (List<Integer> p : permutations) {
            System.out.println(p);
        }
    }
}

---

6. Example Execution Trace

Let’s look at how recursion and backtracking happen for nums = [1,2,3]:

Recursive Depth	Current Path	Used Array	Action
0	[]	[F,F,F]	Start
1	[1]	[T,F,F]	Choose 1
2	[1,2]	[T,T,F]	Choose 2
3	[1,2,3]	[T,T,T]	Add to result
2	[1,2]	[T,T,F]	Backtrack (remove 3)
2	[1,3]	[T,F,T]	Choose 3
3	[1,3,2]	[T,T,T]	Add to result
…	…	…	Continue similarly

---

7. Time and Space Complexity

Time Complexity: O(n × n!)

• There are n! permutations.
• Copying each permutation takes O(n).

Space Complexity: O(n)

• Recursion stack and used array both depend on n.

---

8. Alternative Implementation (Using Swapping)

Another way to generate permutations is in-place swapping, which avoids using extra boolean arrays.

import java.util.*;

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

    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        // Base case
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) permutation.add(num);
            result.add(permutation);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);              // Choose
            backtrack(nums, start + 1, result); // Explore
            swap(nums, start, i);              // Undo (backtrack)
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        PermutationsSwap obj = new PermutationsSwap();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = obj.permute(nums);

        System.out.println("All Permutations (Swap Method):");
        for (List<Integer> p : result) {
            System.out.println(p);
        }
    }
}

---

Comparison of Two Methods

Approach	Description	Extra Space	Simplicity
Boolean used[]	Tracks chosen elements	O(n)	Easier to read
Swapping	Reorders array in place	O(1)	More memory-efficient

---

9. Edge Cases

1. Single element: [1] → [[1]]
2. Two elements: [1,2] → [[1,2],[2,1]]
3. Empty array: [] → []
4. Negative numbers: [0,-1,1] → All permutations are valid.

---

10. Key Takeaways

• Backtracking is ideal for generating combinations, permutations, and subsets.
• Always undo changes after recursive calls to explore new paths.
• The order of recursion + backtracking defines the structure of your solution.
• This is a foundational problem for understanding recursion depth and search trees.