// ─────────────────────────────────────────────────────────────────────────────
// BACKTRACKING
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : DFS over a decision tree; build a partial solution, recurse, undo. Enumerate or search.
// TELL   : "all possible", "generate all", "combinations / permutations / subsets", "place N ...",
//          "valid arrangements", "partition into", constraints small (n <= ~20).
// SAY    : choose / explore / un-choose, decision tree, pruning, state space, start index (combinations)
//          vs used[] (permutations), skip duplicates after sorting, constraint propagation.
// BIG-O  : subsets O(2^n * n); permutations O(n! * n); combinations O(C(n,k) * k). Output-sensitive.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── TEMPLATE
//   function backtrack(path, choices/state):
//     if GOAL(path): result.push([...path]); return      // COPY the path
//     for each choice c in choices:
//       if NOT VALID(c): continue                        // prune
//       path.push(c); mark(c)                            // choose
//       backtrack(path, next state)                      // explore
//       path.pop(); unmark(c)                            // un-choose
//   Combinations/subsets: pass a START index so order does not matter (no repeats).
//   Permutations: pass a used[] array so every element is considered at every position.
//   Duplicates: SORT FIRST, then `if (i > start && a[i] === a[i-1]) continue` (or !used[i-1] for permutations).

// ── 1. Subsets (power set)  —  at each index, include or not; or start-index loop  —  O(2^n * n)
function subsets(nums) {
  const out = [], path = [];
  const bt = (start) => {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) { path.push(nums[i]); bt(i + 1); path.pop(); }
  };
  bt(0);
  return out;
}
assert.deepEqual(subsets([1, 2, 3]), [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]);
assert.deepEqual(subsets([]), [[]]);

// ── 2. Subsets II (with duplicates)  —  sort; skip a[i] === a[i-1] when i > start  —  O(2^n * n)
function subsetsWithDup(nums) {
  nums = [...nums].sort((a, b) => a - b);
  const out = [], path = [];
  const bt = (start) => {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]); bt(i + 1); path.pop();
    }
  };
  bt(0);
  return out;
}
assert.deepEqual(subsetsWithDup([1, 2, 2]), [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]);
assert.deepEqual(subsetsWithDup([0]), [[], [0]]);

// ── 3. Permutations  —  used[] flags; goal when path.length === n  —  O(n! * n)
function permute(nums) {
  const out = [], path = [], used = new Array(nums.length).fill(false);
  const bt = () => {
    if (path.length === nums.length) { out.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      bt();
      path.pop(); used[i] = false;
    }
  };
  bt();
  return out;
}
assert.deepEqual(permute([1, 2, 3]), [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]);
assert.deepEqual(permute([]), [[]]);

// ── 4. Permutations II (with duplicates)  —  sort; skip if a[i] === a[i-1] && !used[i-1]  —  O(n! * n)
function permuteUnique(nums) {
  nums = [...nums].sort((a, b) => a - b);
  const out = [], path = [], used = new Array(nums.length).fill(false);
  const bt = () => {
    if (path.length === nums.length) { out.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue; // same value, earlier twin not used => dup branch
      used[i] = true; path.push(nums[i]);
      bt();
      path.pop(); used[i] = false;
    }
  };
  bt();
  return out;
}
assert.deepEqual(permuteUnique([1, 1, 2]), [[1, 1, 2], [1, 2, 1], [2, 1, 1]]);
assert.deepEqual(permuteUnique([2, 2]), [[2, 2]]);

// ── 5. Combinations C(n, k)  —  start index; prune when remaining < needed  —  O(C(n,k) * k)
function combine(n, k) {
  const out = [], path = [];
  const bt = (start) => {
    if (path.length === k) { out.push([...path]); return; }
    for (let i = start; i <= n - (k - path.length) + 1; i++) { path.push(i); bt(i + 1); path.pop(); } // pruned upper bound
  };
  bt(1);
  return out;
}
assert.deepEqual(combine(4, 2), [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]);
assert.deepEqual(combine(1, 1), [[1]]);

// ── 6. Combination sum I (reuse allowed)  —  recurse with same i; prune when remaining < 0 (sorted => break)  —  O(k^(T/min))
function combinationSum(cands, target) {
  cands = [...cands].sort((a, b) => a - b);
  const out = [], path = [];
  const bt = (start, remain) => {
    if (remain === 0) { out.push([...path]); return; }
    for (let i = start; i < cands.length; i++) {
      if (cands[i] > remain) break; // sorted: nothing further fits
      path.push(cands[i]); bt(i, remain - cands[i]); path.pop(); // i, not i+1 => reuse
    }
  };
  bt(0, target);
  return out;
}
assert.deepEqual(combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]);
assert.deepEqual(combinationSum([2], 1), []);

// ── 7. Combination sum II (each once, duplicates in input)  —  i+1 and skip equal siblings  —  O(2^n)
function combinationSum2(cands, target) {
  cands = [...cands].sort((a, b) => a - b);
  const out = [], path = [];
  const bt = (start, remain) => {
    if (remain === 0) { out.push([...path]); return; }
    for (let i = start; i < cands.length; i++) {
      if (cands[i] > remain) break;
      if (i > start && cands[i] === cands[i - 1]) continue;
      path.push(cands[i]); bt(i + 1, remain - cands[i]); path.pop();
    }
  };
  bt(0, target);
  return out;
}
assert.deepEqual(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8), [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]);
assert.deepEqual(combinationSum2([2, 5, 2, 1, 2], 5), [[1, 2, 2], [5]]);

// ── 8. Generate parentheses  —  add '(' if open < n; add ')' if close < open  —  O(4^n / sqrt(n)) Catalan
function generateParenthesis(n) {
  const out = [];
  const bt = (s, open, close) => {
    if (s.length === 2 * n) { out.push(s); return; }
    if (open < n) bt(s + '(', open + 1, close);
    if (close < open) bt(s + ')', open, close + 1);
  };
  bt('', 0, 0);
  return out;
}
assert.deepEqual(generateParenthesis(3), ['((()))', '(()())', '(())()', '()(())', '()()()']);
assert.deepEqual(generateParenthesis(1), ['()']);

// ── 9. Letter combinations of a phone number  —  digit -> letters; one letter per level  —  O(4^n * n)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' };
  const out = [];
  const bt = (i, s) => {
    if (i === digits.length) { out.push(s); return; }
    for (const ch of map[digits[i]]) bt(i + 1, s + ch);
  };
  bt(0, '');
  return out;
}
assert.deepEqual(letterCombinations('23'), ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']);
assert.deepEqual(letterCombinations(''), []);

// ── 10. N-Queens  —  one queen per row; sets for cols, diag (r-c), anti-diag (r+c)  —  O(n!)
function solveNQueens(n) {
  const boards = [], cols = new Set(), d1 = new Set(), d2 = new Set(), pos = [];
  const bt = (r) => {
    if (r === n) { boards.push(pos.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
      cols.add(c); d1.add(r - c); d2.add(r + c); pos.push(c);
      bt(r + 1);
      cols.delete(c); d1.delete(r - c); d2.delete(r + c); pos.pop();
    }
  };
  bt(0);
  return boards;
}
assert.equal(solveNQueens(4).length, 2);
assert.deepEqual(solveNQueens(4)[0], ['.Q..', '...Q', 'Q...', '..Q.']);
assert.equal(solveNQueens(8).length, 92);
assert.equal(solveNQueens(3).length, 0);

// ── 11. Word search (grid DFS with visited)  —  mark cell '#', explore 4 dirs, restore  —  O(mn * 3^L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  const dfs = (r, c, i) => {
    if (i === word.length) return true;
    if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] !== word[i]) return false;
    const ch = board[r][c];
    board[r][c] = '#';
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = ch;
    return found;
  };
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true;
  return false;
}
const board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']];
assert.equal(exist(board, 'ABCCED'), true);
assert.equal(exist(board, 'ABCB'), false); // cannot reuse a cell
assert.equal(exist([['a']], 'a'), true);

// ── 12. Palindrome partitioning  —  cut at every j where s[start..j] is a palindrome  —  O(n * 2^n)
function partition(s) {
  const out = [], path = [];
  const isPal = (i, j) => { while (i < j) if (s[i++] !== s[j--]) return false; return true; };
  const bt = (start) => {
    if (start === s.length) { out.push([...path]); return; }
    for (let j = start; j < s.length; j++) if (isPal(start, j)) { path.push(s.slice(start, j + 1)); bt(j + 1); path.pop(); }
  };
  bt(0);
  return out;
}
assert.deepEqual(partition('aab'), [['a', 'a', 'b'], ['aa', 'b']]);
assert.deepEqual(partition('a'), [['a']]);

// ── 13. Sudoku solver sketch  —  find empty cell; try 1-9 that pass row/col/box check; recurse; undo on failure  —  O(9^(empty))
function solveSudoku(b) {
  const ok = (r, c, d) => {
    for (let i = 0; i < 9; i++) {
      if (b[r][i] === d || b[i][c] === d) return false;
      if (b[3 * ((r / 3) | 0) + ((i / 3) | 0)][3 * ((c / 3) | 0) + (i % 3)] === d) return false;
    }
    return true;
  };
  const bt = () => {
    for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) if (b[r][c] === '.') {
      for (let d = 1; d <= 9; d++) if (ok(r, c, String(d))) { b[r][c] = String(d); if (bt()) return true; b[r][c] = '.'; }
      return false; // no digit fits: backtrack
    }
    return true; // no empty cell left
  };
  bt();
  return b;
}
const sudoku = ['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'].map((r) => r.split(''));
const solved = solveSudoku(sudoku);
assert.equal(solved[0].join(''), '534678912');
assert.equal(solved[8].join(''), '345286179');
assert.ok(solved.every((row) => new Set(row).size === 9));

console.log('ok: algorithms/backtracking.js');