Faangprep Logo
Log inStart free
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.

Every value gets a turn in every position. Take one from the pool, fill the next slot, and put it back when that branch is done.

READY

Pool

1
2
3

Order

·
·
·

Orderings

0 / 6

 

Nothing placed yet. 6 orderings to find.

Next

Place 1 in position 1.

N

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).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Subsets

Next

N-Queens

Frequently Asked Questions

What are Permutations?

The different ways in which a set of things can be ordered or arranged.

Used Array vs Swapping logic?

Backtracking can generate permutations by either tracking "Used" elements in a boolean array OR by swapping the current index with all subsequent indices.

Total Permutations count?

For a set of N distinct elements, there are N! (factorial) possible permutations.