Faangprep Logo
LoginRegister
Browse Curriculum

Permutations

A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement. Given an array of distinct integers, return all possible permutations.

Permutations

Ready

See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine you have N empty slots and N distinct items. For the first slot, you have N choices. Once you pick an item, you have N-1 items left for the next slot, and so on. This process forms a decision tree where each path from the root to a leaf represents a unique permutation.

Concept

Key Concepts:

  1. Backtracking: Build specific candidates (permutations) incrementally.
  2. State Space Tree: Visualize the process as traversing a tree where each node represents a partial permutation.
  3. Constraints: Each number can only be used once in a single permutation.
  4. Base Case: When the current permutation has the same length as the input array, we've found a valid solution.

How it Works

  1. Define a recursive function backtrack(current_permutation).
  2. Base Case: If current_permutation.length == nums.length, add a copy of it to the result list and return.
  3. Recursive Step: Iterate through each number in the input array.
  4. Check Validity: If the number is already in current_permutation, skip it (or use a visited array/set for O(1) lookups).
  5. Place & Explore: Add the number to current_permutation, recursively call backtrack, then remove the last added number (backtrack) to explore other possibilities.

Step-by-Step Breakdown

Example: Input [1, 2]

  • Start with an empty list: []
  • Step 1: Choose 1. Current: [1]
  • Step 2: Choose 2. Current: [1, 2] -> Valid! Add to results.
  • Step 3: Backtrack. Remove 2. Current: [1]. No other choices.
  • Step 4: Backtrack. Remove 1. Current: [].
  • Step 5: Choose 2. Current: [2]
  • Step 6: Choose 1. Current: [2, 1] -> Valid! Add to results.
  • Final Result: [[1, 2], [2, 1]]

When to Use

  • When you need to generate all possible orderings of a set.
  • Solving optimization problems involving ordering (e.g., Traveling Salesperson Problem - small inputs).
  • Brute-force solutions for puzzles (e.g., Sudoku, Cryptarithmetic) often involve permutation logic.

When NOT to Use

  • When the input size N is large (N > 10), as the number of permutations N! grows factorially.
  • When the order of elements does not matter (use Combinations or Subsets instead).

How to Identify

Keywords like "all arrangements", "all orderings", "reorder". Constraints allow for O(N!) complexity (usually N <= 10).

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep