Permutations

Lesson 11.3 · Medium · Fill the slots · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

List every ordering of the numbers. n items give n! orderings, so 4 items are already 24 results.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

slot 110

·1

·2

·3

Put 1 in slot 1. Unused: [2, 3, 4].

found 0

1 / 129

The idea

Complexity

Time	Space	Why
`O(n × n!)`	`O(n)`	n! orders, each copied in O(n).

In Python

def permutations(nums):
    res, cur, used = [], [], [False] * len(nums)
    def dfs():
        if len(cur) == len(nums):
            res.append(cur[:]); return
        for i, x in enumerate(nums):
            if used[i]: continue
            used[i] = True; cur.append(x)
            dfs()
            cur.pop(); used[i] = False        # backtrack
    dfs()
    return res

</> Now code it →Try it on LeetCode: Permutations →

Summary: say it in the interview

Fill slot 1, then slot 2, and so on. In each slot try every number not yet used. When all slots are filled, record the result. Then free the last number and try the next one.
Time O(n × n!), space O(n). n! orders, each copied in O(n).