\

Permutations

Difficulty: N/A | Solved: December 20, 2025

[[Recursion]]

Problem

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

Brain storming

Brute force

so the logic here is base case , if the current permutation is of the length == nums , we have found a valid input and that has to be added to the results backtracking is

  1. choose
  2. operation
  3. recurse
  4. undo

so for each element in nums we put them on index 0 and we recurse then with the remaing value

nums = [1,2,3]

result = []

def permutations(current_permutation,pivot_index, nums:list[int]):
	# base case
	if len(current_permutation) == nums:
		results.append(current_permutation)
		return
	for i in range(len(nums)):
		pivot_index = i # choose
		# operation
		current_permutation[0] = pivot_index
		permutations(current_permutation, pivot_index, nums) # recurse
		current_permutation.pop(nums[pivot_index]) # undo
		

permutations([], 0, nums)
print(results)
  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-06 08:06) - (end:: 2025-12-06 08:26)

Optimal solution

The goal is to build a permutation of length N. We need to decide which number goes into the first position (index 0), then which number goes into the second position (index 1), and so on.

Let’s think about filling just the first position (index 0) of our array [1, 2, 3].

  • What are the possible numbers we can place at index 0?
  • If we choose 1 to be at index 0, what is the remaining subproblem?
  • If we choose 2 to be at index 0, what is the remaining subproblem?

Choice: Pick an available element (1, 2, or 3) for the current position (index 0).

Subproblem: Solve the exact same problem—“find all permutations”—for the next position (index 1) using the remaining available elements.

Now, the clever part of the standard in-place algorithm is how we manage “placing an element” and tracking “remaining available elements” without using extra memory (like a used_elements set).

Question 2: The “Swap” Mechanic

Imagine you have the array A = [1, 2, 3] and you’re trying to fill index = 0.

  • To place 1 at index 0: The 1 is already there. Great. The “remaining elements” are conveniently at A[1:].
  • To place 2 at index 0: The 2 is currently at index 1. How can you get it to index 0 using a simple, reversible operation?
  • To place 3 at index 0: The 3 is at index 2. How can you get it to index 0?

So, the “Choose” step for permutations is swapping.

Now let’s put it all together. Our function is generate(index, array). Its job is to generate all permutations for the subarray starting from index.

Inside generate(index, array):

  1. We need a loop to make all possible “choices” for the index position. The available choices are all the elements from index to the end of the array.

    • So, for i from index to len(array)-1:

  2. Inside the loop, for each i, we perform our three steps:

    • Choose: Swap the element at i into the index position. swap(array[index], array[i]).
    • Explore: Now that we’ve locked in our choice for index, what is the recursive call to solve for the rest of the array?
    • Undo: After that recursive call returns, we must reverse our “Choose” step to prepare the array for the next iteration of the for loop. What does this “Undo” operation look like?

We will not make a new array to save space rather we will just keep the track of the index , if the index is == len(nums) -1 that means we have reached the end of permutation and we have hit the recursion boundary

nums = [1,2,3]
all_permutations = []

def generate(index, array:list[int]):
	# base case if we have exhausted all the elements from the array
	# we have got a valid permutation
	if index == len(array)-1:
		all_permutations.append(list(array)) # create a COPY and then add
	
	# recursive step
	for i in range(index, len(array)):
		# choose
		array[index], array[i] = array[i] , array[index]
		# explore
		generate(index+1, array)
		# undo
		array[i], array[index] = array[index], array[i]


generate(0, nums)
print(all_permutations)

Comparing with my brute force approach

nums = [1,2,3]

result = []

def permutations(current_permutation,pivot_index, nums:list[int]):
	# base case
	if len(current_permutation) == nums:
		results.append(current_permutation)
		return
	for i in range(len(nums)):
		pivot_index = i # choose
		# operation
		current_permutation[0] = pivot_index
		permutations(current_permutation, pivot_index, nums) # recurse
		current_permutation.pop(nums[pivot_index]) # undo
		

permutations([], 0, nums)
print(results)

Ideal version

# (Assuming all_permutations and the initial array are defined outside)

def generate(index, array):
    # BASE CASE: If the index is at the end, it means we have successfully
    # chosen elements for all positions from 0 to N-1.
    # The array now holds one complete permutation.
    if index == len(array): # A common way is to stop when index reaches the length
        all_permutations.append(list(array)) # Add a copy!
        return

    # RECURSIVE STEP:
    # For the current 'index', try placing every available element there.
    # The available elements are at positions 'index' through the end of the array.
    for i in range(index, len(array)):
        
        # 1. CHOOSE: Place the i-th element into the current 'index' position.
        array[index], array[i] = array[i], array[index]

        # 2. EXPLORE: Generate all permutations for the rest of the array.
        generate(index + 1, array)

        # 3. UNDO: Swap back to restore the array to its original state
        #    for the next iteration of this for loop.
        array[index], array[i] = array[i], array[index]
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-06 08:30) - (end:: 2025-12-06 09:00)
  • 🥤 (pomodoro::BREAK) (duration:: 15m) (begin:: 2025-12-06 12:54) - (end:: 2025-12-06 17:03)