Generating Permutations Using Backtracking

1. Visualizing Permutations as a Decision Tree

Just like with the subsets problem, we can visualize generating permutations as exploring a decision tree. However, there's a key difference: once we use a number in our current permutation, we cannot use it again.

Let's consider the input [1, 2, 3].

• At the first level of our tree, we have three choices for the first position: 1, 2, or 3.
• If we choose 1, our next choice for the second position must come from the remaining numbers: 2 or 3.
• If we then choose 2, the only number left for the final position is 3. This gives us the permutation [1, 2, 3].

This process of making a choice and then narrowing down the subsequent choices is the heart of the backtracking approach for permutations.

2. Applying the "Choose, Explore, Un-choose" Template

Now, how do we translate this decision tree into our backtracking template? We'll use a recursive function that builds a permutation step-by-step.

1. The State: We need to keep track of the permutation we are currently building (let's call it current_permutation) and which numbers from the original input have already been used.
2. The Base Case: Our recursion stops when the length of current_permutation is equal to the length of the original input array. At this point, we have a complete permutation, so we add it to our results.
3. The Choices: At any step, our choices are all the numbers from the original input that we haven't used yet.
4. The Pattern:
   • Choose: Pick an unused number and add it to current_permutation.
   • Explore: Make a recursive call to continue building the permutation from this new state.
   • Un-choose: Once the recursive call returns, remove the number you just added. This backtracks, allowing you to explore other choices for the current position.

Let's see this in action.

3. Implementing the Permutations Algorithm

There are a couple of ways to track which elements have been used. The video mentions checking if x is not in sol. This is simple to write but can be inefficient, as checking for membership in a list takes linear time, O(n).

A more efficient and common pattern in competitive programming is to use a boolean used array. This array is the same size as the input, and used[i] is True if nums[i] is in our current permutation, and False otherwise. Checking used[i] is an O(1) operation, which is much faster.

Let's study an implementation that uses this used array approach.

Here is the code from the article, with our template labels added for clarity.

def permutations(nums):
    result = []
    # `used` array to track which elements are in the current permutation
    used = [False] * len(nums) 
    current = []

    def backtrack():
        # BASE CASE: If the current permutation is complete
        if len(current) == len(nums):
            # Add a copy of the current permutation to the results
            result.append(current[:]) 
            return

        # Iterate through all numbers to find the next choice
        for i in range(len(nums)):
            # CONSTRAINT: Only use numbers that haven't been used yet
            if used[i]:
                continue

            # 1. CHOOSE
            used[i] = True
            current.append(nums[i])

            # 2. EXPLORE
            backtrack()

            # 3. UN-CHOOSE (This is the backtrack step)
            current.pop()
            used[i] = False
    
    backtrack()
    return result

# Example
print(permutations([1, 2, 3]))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Notice the crucial difference from the Subsets problem. In Subsets, we passed a start_index to the recursive call to prevent re-using elements and creating duplicate subsets. Here, for permutations, we must be able to use any number at any position, so our loop always goes from 0 to len(nums). The used array is what prevents us from using the same element twice in a single permutation.

4. Complexity Analysis

For your competitive programming goals, understanding the complexity of your algorithms is vital.

• Time Complexity: The number of permutations is n! (n-factorial). For each complete permutation, we make a copy of the list, which takes O(n) time. The work done in the recursive calls leading up to the n! leaf nodes is also significant. A common way to express the time complexity is O(n * n!). This kind of factorial complexity means the algorithm is only feasible for small values of n (typically n <= 10).

• Space Complexity: The maximum depth of the recursion is n. Both the current list and the recursion call stack will take up space proportional to n. Therefore, the space complexity is O(n) (not including the output list, which stores the n! permutations).

Conclusion

In this lesson, you've successfully applied the general backtracking template to solve the permutations problem. This exercise highlights how a single core pattern can be adapted to solve different problems by carefully defining the constraints.

Key Takeaways:

• Generating permutations is a classic backtracking problem that involves finding all possible orderings of a set.
• The "Choose, Explore, Un-choose" template works perfectly. The key adaptation is adding a constraint to ensure an element is not used more than once in a single permutation.
• Using a boolean used array is an efficient O(1) method for tracking which elements have been chosen.
• The time complexity of generating permutations is factorial, O(n * n!), making it suitable only for small inputs.

Up Next:
We'll continue our exploration of backtracking by tackling Combinations. A combination problem asks for all subsets of a specific size k. You'll see how another small tweak to our base case and recursive logic allows the same powerful template to solve yet another common problem type.