[Algorithm] 14. Backtracking

14. Backtracking

Backtracking is a technique where you try all possible options and backtrack when you hit an invalid state. For this problem, you can recursively generate permutations by picking elements one by one and then swapping them to find new permutations.

1.Permutations (LeetCode #46)

참고자료-굳

Solution1: Swapped

function permute(nums: number[]): number[][] {
  const permutations: number[][] = [];
 
  function backtrackDFS(fixedCharIdx: number) {
    if (fixedCharIdx === nums.length) {
      permutations.push([...nums]);
      return;
    }

    for (let i = fixedCharIdx; i < nums.length; i++) {
      [nums[fixedCharIdx], nums[i]] = [nums[i], nums[fixedCharIdx]];
      backtrackDFS(fixedCharIdx + 1, name);
      [nums[fixedCharIdx], nums[i]] = [nums[i], nums[fixedCharIdx]];
      
    }
  }
  backtrackDFS(0);
  return permutations;
}

Solution1-1:swapped : With call stack console to help understaind

function permute(nums: number[]): number[][] {
  const permutations: number[][] = [];
  const nameList = [
    "Ian",
    "Jessica",
    "Kevin",
    "Lily",
    "Michael",
    "Nora",
    "Oscar",
    "Penelope",
    "Quincy",
    "Rebecca",
    "Steve",
    "Tracy",
    "Ulysses",
    "Violet",
    "Walter",
    "Xena",
  ];
  async function backtrackDFS(fixedCharIdx: number, fromNm: string = "begin") {
    const name = nameList.pop()!;
    console.log(
      "    ".repeat(fixedCharIdx) + "depth ==== ",
      fixedCharIdx,
      "::",
      `fromFnName: ${fromNm}`,
      "->",
      `thisFnName: ${name}`,
      fixedCharIdx === nums.length ? "return" : ""
    );

    if (fixedCharIdx === nums.length) {
      permutations.push([...nums]);
      return;
    }

    for (let i = fixedCharIdx; i < nums.length; i++) {
      // Swap current element with the element at 'start'
      [nums[fixedCharIdx], nums[i]] = [nums[i], nums[fixedCharIdx]];
      console.log(
        "    ".repeat(fixedCharIdx) + "Swapped:",
        name,
        fixedCharIdx,
        "↔",
        i,
        "=>",
        nums
      );

      backtrackDFS(fixedCharIdx + 1, name);
      [nums[fixedCharIdx], nums[i]] = [nums[i], nums[fixedCharIdx]];
      console.log(
        "    ".repeat(fixedCharIdx) + "Backtracked:",
        name,
        fixedCharIdx,
        "↔",
        i,
        "=>",
        nums
      );
    }
  }
  backtrackDFS(0);

  console.log(permutations);
  return permutations;
}

depth ====  0 :: fromFnName: begin -> thisFnName: Xena 
Swapped: Xena 0 ↔ 0 => [ 1, 2, 3 ]
    depth ====  1 :: fromFnName: Xena -> thisFnName: Walter 
    Swapped: Walter 1 ↔ 1 => [ 1, 2, 3 ]
        depth ====  2 :: fromFnName: Walter -> thisFnName: Violet 
        Swapped: Violet 2 ↔ 2 => [ 1, 2, 3 ]
            depth ====  3 :: fromFnName: Violet -> thisFnName: Ulysses return
        Backtracked: Violet 2 ↔ 2 => [ 1, 2, 3 ]
    Backtracked: Walter 1 ↔ 1 => [ 1, 2, 3 ]
    Swapped: Walter 1 ↔ 2 => [ 1, 3, 2 ]
        depth ====  2 :: fromFnName: Walter -> thisFnName: Tracy 
        Swapped: Tracy 2 ↔ 2 => [ 1, 3, 2 ]
            depth ====  3 :: fromFnName: Tracy -> thisFnName: Steve return
        Backtracked: Tracy 2 ↔ 2 => [ 1, 3, 2 ]
    Backtracked: Walter 1 ↔ 2 => [ 1, 2, 3 ]
Backtracked: Xena 0 ↔ 0 => [ 1, 2, 3 ]
Swapped: Xena 0 ↔ 1 => [ 2, 1, 3 ]
    depth ====  1 :: fromFnName: Xena -> thisFnName: Rebecca 
    Swapped: Rebecca 1 ↔ 1 => [ 2, 1, 3 ]
        depth ====  2 :: fromFnName: Rebecca -> thisFnName: Quincy 
        Swapped: Quincy 2 ↔ 2 => [ 2, 1, 3 ]
            depth ====  3 :: fromFnName: Quincy -> thisFnName: Penelope return
        Backtracked: Quincy 2 ↔ 2 => [ 2, 1, 3 ]
    Backtracked: Rebecca 1 ↔ 1 => [ 2, 1, 3 ]
    Swapped: Rebecca 1 ↔ 2 => [ 2, 3, 1 ]
        depth ====  2 :: fromFnName: Rebecca -> thisFnName: Oscar 
        Swapped: Oscar 2 ↔ 2 => [ 2, 3, 1 ]
            depth ====  3 :: fromFnName: Oscar -> thisFnName: Nora return
        Backtracked: Oscar 2 ↔ 2 => [ 2, 3, 1 ]
    Backtracked: Rebecca 1 ↔ 2 => [ 2, 1, 3 ]
Backtracked: Xena 0 ↔ 1 => [ 1, 2, 3 ]
Swapped: Xena 0 ↔ 2 => [ 3, 2, 1 ]
    depth ====  1 :: fromFnName: Xena -> thisFnName: Michael 
    Swapped: Michael 1 ↔ 1 => [ 3, 2, 1 ]
        depth ====  2 :: fromFnName: Michael -> thisFnName: Lily 
        Swapped: Lily 2 ↔ 2 => [ 3, 2, 1 ]
            depth ====  3 :: fromFnName: Lily -> thisFnName: Kevin return
        Backtracked: Lily 2 ↔ 2 => [ 3, 2, 1 ]
    Backtracked: Michael 1 ↔ 1 => [ 3, 2, 1 ]
    Swapped: Michael 1 ↔ 2 => [ 3, 1, 2 ]
        depth ====  2 :: fromFnName: Michael -> thisFnName: Jessica 
        Swapped: Jessica 2 ↔ 2 => [ 3, 1, 2 ]
            depth ====  3 :: fromFnName: Jessica -> thisFnName: Ian return
        Backtracked: Jessica 2 ↔ 2 => [ 3, 1, 2 ]
    Backtracked: Michael 1 ↔ 2 => [ 3, 2, 1 ]
Backtracked: Xena 0 ↔ 2 => [ 1, 2, 3 ]

Solution2

function permute2(nums: number[]): number[][] {
  const permutations: number[][] = [];
  const partialPermutation: number[] = [];

  function backtrack() {
    // Base case: If partialPermutation is complete, push a copy of it
    console.log("when call ---  ----- ", [...partialPermutation]);
    if (partialPermutation.length === nums.length) {
      // Caution! : permutations.push(partialPermutation); // Create a copy of the current permutation
      permutations.push([...partialPermutation]); // Create a copy of the current permutation
      return;
    }

    for (const num of nums) {
      if (!partialPermutation.includes(num)) {
        partialPermutation.push(num);
        backtrack(); // Recurse
        partialPermutation.pop(); // Backtrack
      }
    }
  }

  backtrack(); // Start the backtracking process
  return permutations;
}

2.Subsets (LeetCode #78)

Backtrack

// backtracking
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, currentSubset: number[]) {
    result.push([...currentSubset]);

    for (let i = start; i < nums.length; i++) {
      currentSubset.push(nums[i]);

      backtrack(i + 1, currentSubset);

      currentSubset.pop();
    }
    
  }

  backtrack(0, []);

  return result;
}

3.N-Queens (LeetCode #51)

Time O(N!) / Space O(N)

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];

  // columns: Tracks which columns are already occupied by a queen.
  // diagonals1: Tracks the "main diagonals" (difference between row and column).
  // diagonals2: Tracks the "anti-diagonals" (sum of row and column).
  function backtrack(
    row: number,
    columns: Set<number>,
    mainDiagonals: Set<number>,
    antiDiagonals: Set<number>,
    currentBoard: string[]
  ) {
    if (row === n) {
      result.push([...currentBoard]);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (
        columns.has(col) ||
        mainDiagonals.has(row - col) ||
        antiDiagonals.has(row + col)
      ) {
        continue;
      }

      currentBoard[row] = ".".repeat(col) + "Q" + ".".repeat(n - col - 1);
      columns.add(col);
      mainDiagonals.add(row - col);
      antiDiagonals.add(row + col);

      backtrack(row + 1, columns, mainDiagonals, antiDiagonals, currentBoard);

      columns.delete(col);
      mainDiagonals.delete(row - col);
      antiDiagonals.delete(row + col);
    }
  }

  backtrack(0, new Set(), new Set(), new Set(), Array(n).fill(""));

  return result;
}