Permutations with Backtracking and Swaps

1. The Core Idea: Fix, Permute, and Swap

The problem of finding all permutations of n elements can be broken down recursively. The main idea is to:

1. Fix an element for the first position.
2. Permute the remaining n-1 elements.
3. Repeat this process by placing every available element into the first position.

How can we do this efficiently? Instead of using extra data structures to keep track of used elements (like a boolean array or a HashSet), we can perform the operation in-place within the array itself using swaps.

The strategy for an array nums at a given index is:

• Iterate from i = index to the end of the array.
• In each iteration, swap the element at index with the element at i. This effectively places the i-th element at the index-th position.
• After the swap, we have "fixed" the element at index. We then make a recursive call to generate all permutations for the rest of the array, starting from index + 1.
• Once the recursive call returns, we swap back the elements to restore the array to its original state. This is the crucial backtracking step, ensuring that the next iteration of the loop works with a clean slate.

Let's watch a video that provides an excellent visualization of this process.

This recursion tree illustrates the process beautifully. At each level, we decide which number gets to be in the current position, and then we recursively solve the problem for the positions that follow.

2. Implementation in Java: The Backtracking Pattern

Now, let's translate this logic into a Java implementation. The structure will feel familiar after our lesson on subsets, but the core logic inside the loop is different.

To understand the complete logic and the importance of each step, this article provides a clear, annotated code example.

Code Deconstruction

Here is a clean implementation based on the resources. This is the pattern you'll want to have ready for interviews.

import java.util.ArrayList;
import java.util.List;
import java.util.Collections; // For Collections.swap if using a List

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 index, int[] nums, List<List<Integer>> result) {
        // Base Case: If the index reaches the end, we have a complete permutation.
        if (index == nums.length) {
            // Create a new list and copy the elements from the current state of `nums`.
            List<Integer> currentPermutation = new ArrayList<>();
            for (int num : nums) {
                currentPermutation.add(num);
            }
            result.add(currentPermutation);
            return;
        }

        // Recursive Step: Iterate through the elements from the current index to the end.
        for (int i = index; i < nums.length; i++) {
            // 1. Make a choice: Swap the current element `i` into the `index` position.
            swap(nums, index, i);

            // 2. Recurse: Explore permutations for the rest of the array.
            backtrack(index + 1, nums, result);

            // 3. Backtrack: Undo the choice by swapping back.
            swap(nums, index, i);
        }
    }

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

Key Points to Analyze:

1. index Parameter: This parameter tracks the current position we are trying to fill. The recursion depth is directly tied to this index.

2. Base Case: if (index == nums.length): When our index has moved past the last element, it means we have successfully placed an element in every position from 0 to n-1. At this point, the nums array itself holds one complete permutation. We add a copy of it to our results.

3. The Loop and Swap: The loop for (int i = index; ...) is the engine of our exploration.

   • swap(nums, index, i): This is the action. We are choosing the i-th element to be placed at the index-th position.
   • backtrack(index + 1, ...): This is the recursion. We trust that the function will handle all permutations for the subarray starting at index + 1.
   • swap(nums, index, i) (the second time): This is the backtrack. After returning from the recursion, we undo our swap. This is vital! It ensures that when the loop proceeds to i+1, the array is in the same state as it was before we decided to place the i-th element, allowing us to correctly place the (i+1)-th element at the index position next.

3. A Critical Insight: Why does the loop start from index?

A common point of confusion is why the inner loop starts from i = index and not i = 0. If we started from i = 0 every time, we would generate redundant permutations. By starting from index, we ensure we only swap with elements that have not yet been fixed in the prefix 0...index-1.

This next video segment explains this exact point very well. Although the audio is in Hindi, the visual animation and code clearly demonstrate the logic.

4. Complexity Analysis

For any interview, you need to know the complexity. Given your background, this should be a straightforward analysis.

• Time Complexity: O(N × N!)

  • How many permutations are there for N distinct elements? N! (N factorial).
  • The recursion tree has N! leaf nodes, and each leaf node corresponds to one complete permutation.
  • At each leaf node, we perform an O(N) operation to copy the current state of the array into a new list to be added to our results.
  • Thus, the total time complexity is dominated by this collection step, resulting in O(N × N!).

• Space Complexity: O(N) (Auxiliary Space)

  • The primary space used by the algorithm itself (excluding the output list) is the recursion call stack.
  • The maximum depth of the recursion is N. Therefore, the auxiliary space complexity is O(N).
  • If you are asked to include the space for the output, it would be O(N × N!), as we store N! permutations, each of length N. Always clarify this with your interviewer!

You can review this analysis in the take U forward video (LINK) from timestamp 13:30 to 14:30.

Conclusion

Today we've added a powerful and efficient pattern to your backtracking toolkit. The swap-based method for permutations is elegant because it avoids the overhead of extra space for tracking state, modifying the input array directly.

Key Takeaways:

• Permutations are about arrangement, while subsets are about selection.
• The core strategy is to fix a position, explore possibilities for it, and recurse on the remainder of the array.
• The swap(index, i) followed by backtrack(index + 1) and then swap(index, i) again is the fundamental pattern for this problem.
• Starting the exploration loop from i = index is crucial for avoiding duplicate work and generating correct, unique permutations.
• Be ready to discuss the O(N × N!) time and O(N) auxiliary space complexity.

Preview of the Next Lesson:
We've covered subsets (order doesn't matter, any size) and permutations (order matters, size N). In the next lesson, we will look at combinations. This can be seen as a hybrid: we will generate all subsets of a specific size k. This will require us to adapt the backtracking logic we learned for subsets to handle the size constraint.