#46

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Permutations

Generate all possible orderings of a distinct integer array using backtracking search with careful pruning to avoid duplicates.

array backtracking

Problem Statement

Given an array of distinct integers nums, generate every possible permutation and return them in any order. Each permutation should contain all elements of nums exactly once.

For example, with nums = [1,2,3], valid outputs include [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Constraints ensure 1 <= nums.length <= 6, -10 <= nums[i] <= 10, and all elements are unique.

Examples

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 details omitted.

Example 2

Input: nums = [0,1]

Output: [[0,1],[1,0]]

Example details omitted.

Example 3

Input: nums = [1]

Output: [[1]]

Example details omitted.

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution Approach

Backtracking with a 'used' marker array

Track which elements are already included in the current permutation using a boolean array. At each step, iterate through nums and skip elements marked as used. Recursively add unused elements and backtrack by unmarking them once the recursion unwinds.

Recursive swap method

Swap each element with the current position index to generate permutations in-place. After recursive calls, swap back to restore the array state. This avoids extra space for a 'used' array and allows permutations to be built directly within nums.

Pruning to prevent redundant paths

Even with distinct elements, pruning can stop recursion early if certain paths cannot lead to new permutations. For larger inputs or extensions with duplicate elements, pruning prevents revisiting combinations that are already included in the result list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n! * n) due to generating n! permutations and copying them into the result. Space complexity is O(n) for recursion depth and O(n) for used markers or swaps.

What Interviewers Usually Probe

Candidate immediately considers backtracking and marks elements used for recursion.
Candidate identifies recursion depth and correctly restores state during backtracking.
Candidate demonstrates understanding of how to prune or skip redundant recursion paths.

Common Pitfalls or Variants

Common pitfalls

Failing to restore element state after recursive calls leads to incorrect permutations.
Ignoring the need for a 'used' marker or proper swap tracking can cause duplicates or missing permutations.
Not handling recursion base cases correctly, especially when building the final permutation list.

Follow-up variants

Generate permutations of a string of distinct characters instead of integers.
Generate k-length permutations from n elements instead of full-length permutations.
Generate permutations allowing duplicate elements and remove duplicates from the result list.

FAQ

What is the main strategy to solve the Permutations problem?

Use backtracking search with a 'used' marker or in-place swaps, recursively building permutations and pruning invalid paths.

Can I generate permutations without extra space?

Yes, the recursive swap method allows in-place generation of permutations, reducing space usage compared to a separate 'used' array.

How does pruning work in this context?

Pruning skips recursive paths that cannot produce new unique permutations, ensuring the algorithm doesn't redo work unnecessarily.

What are common mistakes in coding this problem?

Not restoring array state after recursion, failing to mark elements as used, and mishandling base cases can cause errors.

How does the backtracking pattern help with permutations?

Backtracking systematically explores all ordering options, building partial solutions while removing invalid choices through pruning and used tracking.

terminal

Solution

Solution 1: DFS (Backtracking)

We design a function $dfs(i)$ to represent that the first $i$ positions have been filled, and now we need to fill the $i+1$ position. We enumerate all possible numbers, if this number has not been filled, we fill in this number, and then continue to fill the next position, until all positions are filled.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i >= n:
                ans.append(t[:])
                return
            for j, x in enumerate(nums):
                if not vis[j]:
                    vis[j] = True
                    t[i] = x
                    dfs(i + 1)
                    vis[j] = False

        n = len(nums)
        vis = [False] * n
        t = [0] * n
        ans = []
        dfs(0)
        return ans

Continue Practicing

#47 permutations ii #51 n queens #40 combination sum ii