Permutations — Backtracking Visualization

Problem Statement

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

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 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Interactive Visualization

Configuration

Input Array (comma-separated distinct integers):

Controls

Speed: 800ms

Algorithm State

Available Elements

Current Permutation

Collected Results (0)

Decision Tree

Code

fun permute(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()

    fun backtrack(current: MutableList<Int>) {
        if (current.size == nums.size) {
            result.add(current.toList())
            return }

        for (num in nums) {
            if (num !in current) {
                current.add(num)
                backtrack(current)
                current.removeLast()
            } } }
    backtrack(mutableListOf())
    return result }

def permute(nums):
    result = []

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return

        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()

    backtrack([])
    return result

Execution Log

How It Works

Algorithm Overview

The backtracking approach to generating permutations explores all possible orderings by building permutations one element at a time. At each position, we try every element that hasn't been used yet, recurse to fill the remaining positions, then backtrack to try other possibilities.

Key Concepts

Decision Tree: Each level of the tree represents a position in the permutation. Each branch represents choosing a particular unused element for that position.
Used/Unused Tracking: We maintain which elements have been used in the current permutation (by checking if they're already in the current array).
Base Case: When the current permutation has the same length as the input array, we've found a complete permutation and add it to our results.
Backtracking: After exploring all possibilities with a chosen element, we remove it (pop) and try the next element.

Visualization Features

Available Elements: Shows which elements can still be chosen (unused) vs. already used in current permutation
Current Permutation: Displays the permutation being built at each step
Decision Tree: Visual representation of the recursive exploration - each node shows the current permutation state
Results Collection: All complete permutations found are displayed and highlighted when discovered

Time Complexity

O(n! × n) — There are n! permutations to generate, and each one takes O(n) time to construct and copy.

Space Complexity

O(n! × n) — Storing all n! permutations, each of length n. The recursion depth is O(n).