Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Backtracking

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Permutations

Problem (restated)

Given a list of distinct integers, return all possible permutations.

Intuition

Backtracking: choose an unused number, recurse, undo. When path length == n, record a copy.

Approaches

Backtracking with used flags

Tested only
Time O(n · n!)Space O(n)

Idea. path list + used boolean array. Try each unused index, recurse, pop.

Walkthrough. [1,2,3] explores 6 permutations.

Trade-offs. Swap-based in-place generation uses less auxiliary memory for path but is harder to read.

Solution
export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]!);
      dfs();
      path.pop(); used[i] = false;
    }
  };
  dfs();
  return res;
}

export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]!);
      dfs();
      path.pop(); used[i] = false;
    }
  };
  dfs();
  return res;
}

Template connection

Choose / explore / undo. pure backtracking template.

Reflection