Start learning free

LESSON 353 OF 536 · BACKTRACKING

Permutations in Python: Backtracking with a Used List

Practice O(n · n!) Read the full explanation

Given a list nums of distinct integers, return every permutation of nums: every way to put all of its numbers in a row, each number exactly once.

Return the permutations in the order you get by filling the positions from first to last and always trying the numbers in their order in nums: every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on. Among the permutations with the same first number, the second number decides the same way, trying the numbers that are left in their order in nums; then the third, and so on. So nums itself always comes first, and nums reversed comes last.

 

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]]
Explanation: Two permutations start with 1, then two with 2, then two with 3.
After 1, the numbers left are 2 and 3, tried in that order, so [1,2,3] comes before [1,3,2].

Example 2:

Input: nums = [3,1,2]
Output: [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]
Explanation: The numbers are tried in their order in nums, 3 then 1 then 2, not in ascending order.
After 1, the numbers left are 3 and 2, in that order in nums, so [1,3,2] comes before [1,2,3].

Example 3:

Input: nums = [1]
Output: [[1]]
Explanation: One number can be put in a row in only one way.

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Build a permutation one position at a time in a list current, and keep a list used of True/False values, one per number, that says which numbers current already holds. For the next position, go through the numbers in order and skip the used ones; for each unused number, take it (mark it used and add it to current), fill the remaining positions with a recursive call, then give it back (remove it and mark it unused) so the next number can take its place. When current holds all n numbers, save a copy of it. Trying the numbers in their order in nums gives exactly the order above.

There are n! permutations. Copying each one takes n steps, and the calls that build them, fewer than e · n! in all, each loop over the n numbers, so the time is O(n · n!). Besides the answer, the extra space is O(n): current, used and one call per position.

STEP 1 OF 14
    Ctrl + Enter to check

    PYTHON · BACKTRACKING

    Permutations in Python, explained

    Problem overview

    The method permute receives a list nums of distinct integers and returns every permutation of it: every way to put all the numbers in a row, each exactly once.

    The order of the permutations is fixed. The method fills the positions from first to last and always tries the numbers in their order in nums. Every permutation starting with nums[0] comes first, then every one starting with nums[1], and so on. Among permutations with the same first number, the second number decides the same way. So nums itself is always first and nums reversed is always last.

    For nums = [1, 2, 3] the result is:

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

    Two permutations start with 1, two with 2 and two with 3. For nums = [3, 1, 2] the numbers are tried in the order 3, 1, 2, not in ascending order, so the result is [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]]. For nums = [1] it is [[1]].

    Approach: fill one position at a time

    Think of a row of empty slots, with one slot per number. The first slot can take any of the n numbers, the second can take any of the n - 1 that are left, and so on. The count is n * (n - 1) * ... * 1, which is n!. For 8 numbers that is 40,320 permutations.

    Backtracking builds them one slot at a time:

    • Keep a list current with the numbers placed so far, and a list used of True/False values, one per number, that says which numbers current already holds.
    • When current has as many numbers as nums, it is a whole permutation, so save a copy.
    • Otherwise go through the numbers in order. Skip the used ones. For each free one, take it (mark it used and add it to current), fill the rest of the slots with a recursive call, then give it back (remove it and mark it free), so the next number can take its place.

    The loop always starts at index 0 and moves up, which is what yields the order the statement describes. Giving the number back is the "back" in backtracking: when the recursive call returns, current and used are exactly as they were before it, so the loop can try the next candidate for the same slot.

    Step by step

    1. Create result as an empty list of permutations.
    2. Create used as [False] * len(nums). used[i] says whether nums[i] is already in the permutation being built. At the start, every number is free.
    3. Start the search with self.backtrack(nums, used, [], result): no slot is filled yet. The helper comes next.
    4. Return result. The helper adds to this same list.
    5. Declare the helper backtrack(self, nums, used, current, result). Each call fills one more slot of current and calls itself for the rest.
    6. Test whether current is full: len(current) == len(nums). A full list holds every number once.
    7. Save a copy and return. current.copy() is a snapshot, because current keeps changing.
    8. Loop with i over range(len(nums)): every number that could fill the next slot, in the order of nums.
    9. Skip used numbers with if used[i]: continue. A number can't appear twice in a permutation.
    10. Mark the number by setting used[i] = True, so deeper calls won't take it.
    11. Add it to current with append. This fills the slot.
    12. Recurse with self.backtrack(nums, used, current, result). Nothing else needs passing, because used and current already describe what is taken.
    13. Remove the number from the end of current with pop().
    14. Unmark it by setting used[i] = False, so later permutations can use it in another position.

    The solution in Python

    class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        self.backtrack(nums, used, [], result)
        return result
    def backtrack(self, nums, used, current, result):
        if len(current) == len(nums):
            result.append(current.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            self.backtrack(nums, used, current, result)
            current.pop()
            used[i] = False

    Python details worth a closer look:

    • Repeating a list. [False] * 3 is [False, False, False]. Multiplying a list of immutable values like booleans is safe. Multiplying a list of lists would repeat references to the same inner list, which is a different trap.
    • continue. It skips the rest of the current turn of the loop and goes on with the next i, so the code below it only runs for free numbers.
    • Shared lists. used and current are passed by reference: every call sees and changes the same two lists. That makes the marking and the undo work, and it is why the saved permutation must be a copy of current.
    • The undo must be complete. Taking a number changes two things, used and current, and giving it back must undo both. If the line used[i] = False is missing, the first permutation is found and nothing else: for [1, 2, 3] the result is just [[1, 2, 3]], because the numbers stay marked as taken.
    • Indexes, not values. used is indexed by position in nums, not by number. That keeps it correct for negative numbers and for any values, since the lesson only needs the numbers to be distinct.

    Complexity

    Time: O(n * n!). There are n! permutations, and copying one takes n steps. The calls that build them, fewer than e * n! in all, each loop over the n numbers, which keeps the total at O(n * n!).

    Space: O(n) besides the answer. The extra memory is current, used and one call on the stack per slot. The answer itself holds n! lists and is output, so it isn't counted.

    Edge cases and common mistakes

    • One number. [1] gives [[1]]: a single slot has a single way to be filled.
    • The order of tries. [3, 1, 2] starts with 3, because the loop follows the order of nums. Sorting nums first would change the answer's order and fail the lesson's tests.
    • Forgetting the copy. Appending current itself stores one list many times, and at the end that list is empty.
    • Undoing only one of the two changes. Leaving a number marked as used loses permutations, as shown above. Leaving a number in current makes current too long, and the lists that get saved are wrong.

    Testing

    • nums = [1, 2, 3] gives [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
    • nums = [3, 1, 2] gives [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]].
    • nums = [1] gives [[1]].
    • nums = [0, 1, 2, 3, 4, 5, 6, 7] gives a list of 40320 permutations.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free