Permutations of Distinct Values

Interview Problem Interview Medium Constraint Satisfaction Array Backtracking

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.permute(nums). nums contains distinct integers. Return every permutation; permutation order does not matter, but value order inside each permutation does.

Starter code

class Solution:
    def permute(self, nums):
        pass

Test cases

three-values

{
  "args": [
    [
      1,
      2,
      3
    ]
  ]
}

Expected: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Wizard outline

Step 1: Initialize Solution.permute
Replace the empty starter with the first real state owned by Solution.permute. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Single case
Complete the readable core algorithm for one representative Interview case. Track which positions are already used and undo each choice after returning.
Step 4: Harden the Two Values boundary
Repair the reviewed boundary and pass the complete submission contract. At depth d the path is an ordered selection of d distinct input positions. Trying every unused position extends it with every possible next value, so all n! permutations appear exactly once.

Footguns and prerequisites

Membership in the current value path is safe here only because input values are distinct.
recursion and backtracking

Reviewed references

Practice prerequisites

Complete One Backtracking Frame(opens in a new tab)
Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing permutations as a complete Interview Problem.

Recommended approach and implementation

Backtrack over unused positions, mark one used, recurse, then unmark it.

Why it works: At depth d the path is an ordered selection of d distinct input positions. Trying every unused position extends it with every possible next value, so all n! permutations appear exactly once.

class Solution:
    def permute(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        result = []
        path = []
        used = [False] * len(nums)
        def backtrack():
            if len(path) == len(nums):
                result.append(path[:])
                return
            for index, value in enumerate(nums):
                if used[index]:
                    continue
                used[index] = True
                path.append(value)
                backtrack()
                path.pop()
                used[index] = False
        backtrack()
        return result

Similar exercises

Power Set of Distinct Values(opens in a new tab)