Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?