Hide sidebar
leetcode/DSA courseSystem Design

Permutations

Permutations

BacktrackingRecursion
MediumLeetCode #46
20 min

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example

Example 1:

Input: nums = [1,2,3]

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

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution

To generate all permutations, we can use a backtracking algorithm. The idea is to build a permutation step by step. For each position, we try placing every available number. We use a `used` array to keep track of which numbers have been placed in the current permutation.

Algorithm Steps

  • Define a recursive function `backtrack(currentPermutation)`.
  • If the `currentPermutation` has the same length as `nums`, we've found a complete permutation. Add it to our results and return.
  • Iterate through all numbers in `nums`.
    • If the number at index `i` has already been used, skip it.
    • Mark `nums[i]` as used.
    • Add `nums[i]` to `currentPermutation`.
    • Recursively call `backtrack(currentPermutation)`.
    • Backtrack: remove `nums[i]` from `currentPermutation` and unmark it as used.
  • Initial call: `backtrack([])`.

Permutations Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Input Array

1
2
3

Current Permutation

[
1
,
2
,
3
]

Valid Solutions

No solutions found yet...

Permutations Solution

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        res = []
        
        def backtrack(start):
            if start == len(nums):
                res.append(nums[:])
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start] # backtrack
        
        backtrack(0)
        return res