function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const used = new Set<number>();

  function backtrack(path: number[]) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (const num of nums) {
      if (!used.has(num)) {
        used.add(num);
        path.push(num);
        backtrack(path);
        path.pop();
        used.delete(num);
      }
    }
  }

  backtrack([]);
  return result;
}

function combine(n: number, k: number): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, path: number[]) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    for (let i = start; i <= n; i += 1) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

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

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

    for (let i = start; i < nums.length; i += 1) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board = Array.from({ length: n }, () => Array(n).fill('.'));

  function isValid(row: number, col: number): boolean {
    for (let i = 0; i < row; i += 1) {
      if (board[i][col] === 'Q') return false;
      if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
      if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
    }
    return true;
  }

  function backtrack(row: number) {
    if (row === n) {
      result.push(board.map((r) => r.join('')));
      return;
    }

    for (let col = 0; col < n; col += 1) {
      if (isValid(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }

  backtrack(0);
  return result;
}