DSA AnimatorDSA animations
Permutations LC #46 Medium Backtracking · Used Array
Problem

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]]
Explanation: 3! = 6 permutations.
Example 2
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Constraints: 1 ≤ nums.length ≤ 6  |  −10 ≤ nums[i] ≤ 10  |  All integers are unique.
Try Examples
Custom:
Approach
Backtracking with used[] Array
Track which elements are in the current path with a boolean[] used. At each level, try ALL indices (not just start) but skip used[i]=true. Base: curr.size()==n → found permutation.
Input Array
Current Permutation
curr = [ ] (empty)
Results 0 found
Recursion Tree
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Use boolean[] used to track which elements are in current permutation
2
At each level, try ALL indices 0..n-1; skip if used[i]=true
3
Base case: curr.size() == n → permutation complete, add to results
4
n! total permutations for n distinct elements
Time
O(n·n!)
Space
O(n)
Why Backtracking Works

Unlike subsets, permutations use every element exactly once, so we iterate from index 0 each time (not a start index) but skip used[i] elements. The used array prevents including the same element twice in one permutation. Backtracking resets used[i]=false to try the next choice.

How to solve Permutations

LeetCode 46 · Medium · Backtracking · Pattern: Backtracking with Used Set

Why the obvious approach is slow

Writing nested loops only works for a fixed n. Backtracking builds one position at a time for any n.

The key idea

At each level, try every number that is not used yet. Mark it as used, recurse to fill the next position, then unmark it. When the path has n numbers, record it.

Remember

Permutations use a used array instead of a start index. Every unused number can go in the next position.

Run the animation above on your own input, or watch the 1:12 video explanation of Permutations with a dry run and Java code.

More Backtracking problems