Backtracking

def permute(nums: list[int]) -> list[list[int]]:
    """Every ordering of the distinct numbers in `nums`."""
    result: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path[:])  # Every position is filled: a leaf. Save a copy.
            return
        for i in range(len(nums)):
            if used[i]:
                continue  # Already placed earlier in this ordering.
            used[i] = True  # Choose nums[i] for the next position.
            path.append(nums[i])
            backtrack()  # Explore: fill the remaining positions.
            path.pop()  # Un-choose, so nums[i] is free for a later position.
            used[i] = False

    backtrack()
    return result


if __name__ == "__main__":
    print(permute([1, 2, 3]))  # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    print(permute([0, 1]))  # [[0, 1], [1, 0]]
    print(permute([1]))  # [[1]]

// Every ordering of the distinct numbers in `nums`.
export function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array<boolean>(nums.length).fill(false);

  function backtrack(): void {
    if (path.length === nums.length) {
      result.push([...path]); // Every position is filled: a leaf. Save a copy.
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // Already placed earlier in this ordering.
      used[i] = true; // Choose nums[i] for the next position.
      path.push(nums[i]);
      backtrack(); // Explore: fill the remaining positions.
      path.pop(); // Un-choose, so nums[i] is free for a later position.
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3]))); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(JSON.stringify(permute([0, 1]))); // [[0,1],[1,0]]
console.log(JSON.stringify(permute([1]))); // [[1]]

package main

import (
	"fmt"
	"slices"
)

// permute returns every ordering of the distinct numbers in nums.
func permute(nums []int) [][]int {
	result := [][]int{}
	path := []int{}
	used := make([]bool, len(nums))
	var backtrack func()
	backtrack = func() {
		if len(path) == len(nums) {
			result = append(result, slices.Clone(path)) // Every position is filled: a leaf. Save a copy.
			return
		}
		for i := range nums {
			if used[i] {
				continue // Already placed earlier in this ordering.
			}
			used[i] = true // Choose nums[i] for the next position.
			path = append(path, nums[i])
			backtrack()               // Explore: fill the remaining positions.
			path = path[:len(path)-1] // Un-choose, so nums[i] is free for a later position.
			used[i] = false
		}
	}
	backtrack()
	return result
}

func main() {
	fmt.Println(permute([]int{1, 2, 3})) // [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
	fmt.Println(permute([]int{0, 1}))    // [[0 1] [1 0]]
	fmt.Println(permute([]int{1}))       // [[1]]
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Every ordering of the distinct numbers in nums.
    public static List<List<int>> Permute(int[] nums)
    {
        var result = new List<List<int>>();
        var path = new List<int>();
        var used = new bool[nums.Length];

        void Backtrack()
        {
            if (path.Count == nums.Length)
            {
                result.Add(new List<int>(path)); // Every position is filled: a leaf. Save a copy.
                return;
            }
            for (int i = 0; i < nums.Length; i++)
            {
                if (used[i]) continue; // Already placed earlier in this ordering.
                used[i] = true; // Choose nums[i] for the next position.
                path.Add(nums[i]);
                Backtrack(); // Explore: fill the remaining positions.
                path.RemoveAt(path.Count - 1); // Un-choose, so nums[i] is free for a later position.
                used[i] = false;
            }
        }

        Backtrack();
        return result;
    }

    public static void Main()
    {
        Console.WriteLine(Format(Permute(new[] { 1, 2, 3 }))); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
        Console.WriteLine(Format(Permute(new[] { 0, 1 }))); // [[0, 1], [1, 0]]
        Console.WriteLine(Format(Permute(new[] { 1 }))); // [[1]]
    }

    static string Format(List<List<int>> lists) =>
        "[" + string.Join(", ", lists.Select(l => "[" + string.Join(", ", l) + "]")) + "]";
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // Every ordering of the distinct numbers in nums.
    static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }

    static void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // Every position is filled: a leaf. Save a copy.
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // Already placed earlier in this ordering.
            used[i] = true; // Choose nums[i] for the next position.
            path.add(nums[i]);
            backtrack(nums, used, path, result); // Explore: fill the remaining positions.
            path.remove(path.size() - 1); // Un-choose, so nums[i] is free for a later position.
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(permute(new int[] {1, 2, 3})); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
        System.out.println(permute(new int[] {0, 1})); // [[0, 1], [1, 0]]
        System.out.println(permute(new int[] {1})); // [[1]]
    }
}

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """Every unique combination of `candidates` that sums to `target`, where each
    candidate can be used any number of times. Each combination is ascending."""
    candidates = sorted(candidates)
    result: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])  # Hit the target exactly. Save a copy.
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # Sorted, so every later candidate is too big too.
            path.append(candidates[i])  # Choose candidates[i].
            backtrack(i, remaining - candidates[i])  # Explore from i, not i + 1: reuse is allowed.
            path.pop()  # Un-choose.

    backtrack(0, target)
    return result


if __name__ == "__main__":
    print(combination_sum([2, 3, 6, 7], 7))  # [[2, 2, 3], [7]]
    print(combination_sum([2, 3, 5], 8))  # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
    print(combination_sum([2], 1))  # []

// Every unique combination of `candidates` that sums to `target`, where each
// candidate can be used any number of times. Each combination is ascending.
export function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...path]); // Hit the target exactly. Save a copy.
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // Sorted, so every later candidate is too big too.
      path.push(sorted[i]); // Choose sorted[i].
      backtrack(i, remaining - sorted[i]); // Explore from i, not i + 1: reuse is allowed.
      path.pop(); // Un-choose.
    }
  }

  backtrack(0, target);
  return result;
}

console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7))); // [[2,2,3],[7]]
console.log(JSON.stringify(combinationSum([2, 3, 5], 8))); // [[2,2,2,2],[2,3,3],[3,5]]
console.log(JSON.stringify(combinationSum([2], 1))); // []

package main

import (
	"fmt"
	"slices"
)

// combinationSum returns every unique combination of candidates that sums to
// target, where each candidate can be used any number of times. Each
// combination is ascending.
func combinationSum(candidates []int, target int) [][]int {
	sorted := slices.Clone(candidates)
	slices.Sort(sorted)
	result := [][]int{}
	path := []int{}
	var backtrack func(start, remaining int)
	backtrack = func(start, remaining int) {
		if remaining == 0 {
			result = append(result, slices.Clone(path)) // Hit the target exactly. Save a copy.
			return
		}
		for i := start; i < len(sorted); i++ {
			if sorted[i] > remaining {
				break // Sorted, so every later candidate is too big too.
			}
			path = append(path, sorted[i])    // Choose sorted[i].
			backtrack(i, remaining-sorted[i]) // Explore from i, not i + 1: reuse is allowed.
			path = path[:len(path)-1]         // Un-choose.
		}
	}
	backtrack(0, target)
	return result
}

func main() {
	fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7)) // [[2 2 3] [7]]
	fmt.Println(combinationSum([]int{2, 3, 5}, 8))    // [[2 2 2 2] [2 3 3] [3 5]]
	fmt.Println(combinationSum([]int{2}, 1))          // []
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Every unique combination of candidates that sums to target, where each
    // candidate can be used any number of times. Each combination is ascending.
    public static List<List<int>> CombinationSum(int[] candidates, int target)
    {
        var sorted = candidates.OrderBy(c => c).ToArray();
        var result = new List<List<int>>();
        var path = new List<int>();

        void Backtrack(int start, int remaining)
        {
            if (remaining == 0)
            {
                result.Add(new List<int>(path)); // Hit the target exactly. Save a copy.
                return;
            }
            for (int i = start; i < sorted.Length; i++)
            {
                if (sorted[i] > remaining) break; // Sorted, so every later candidate is too big too.
                path.Add(sorted[i]); // Choose sorted[i].
                Backtrack(i, remaining - sorted[i]); // Explore from i, not i + 1: reuse is allowed.
                path.RemoveAt(path.Count - 1); // Un-choose.
            }
        }

        Backtrack(0, target);
        return result;
    }

    public static void Main()
    {
        Console.WriteLine(Format(CombinationSum(new[] { 2, 3, 6, 7 }, 7))); // [[2, 2, 3], [7]]
        Console.WriteLine(Format(CombinationSum(new[] { 2, 3, 5 }, 8))); // [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
        Console.WriteLine(Format(CombinationSum(new[] { 2 }, 1))); // []
    }

    static string Format(List<List<int>> lists) =>
        "[" + string.Join(", ", lists.Select(l => "[" + string.Join(", ", l) + "]")) + "]";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    // Every unique combination of candidates that sums to target, where each
    // candidate can be used any number of times. Each combination is ascending.
    static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] sorted = candidates.clone();
        Arrays.sort(sorted);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(sorted, 0, target, new ArrayList<>(), result);
        return result;
    }

    static void backtrack(int[] sorted, int start, int remaining, List<Integer> path,
            List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path)); // Hit the target exactly. Save a copy.
            return;
        }
        for (int i = start; i < sorted.length; i++) {
            if (sorted[i] > remaining) break; // Sorted, so every later candidate is too big too.
            path.add(sorted[i]); // Choose sorted[i].
            backtrack(sorted, i, remaining - sorted[i], path, result); // Explore from i, not i + 1: reuse is allowed.
            path.remove(path.size() - 1); // Un-choose.
        }
    }

    public static void main(String[] args) {
        System.out.println(combinationSum(new int[] {2, 3, 6, 7}, 7)); // [[2, 2, 3], [7]]
        System.out.println(combinationSum(new int[] {2, 3, 5}, 8)); // [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
        System.out.println(combinationSum(new int[] {2}, 1)); // []
    }
}

def solve_n_queens(n: int) -> list[list[str]]:
    """Every way to place n queens on an n x n board so no two attack each other.
    Each board is a list of rows, with "Q" for a queen and "." for an empty square."""
    result: list[list[str]] = []
    queens = [0] * n  # queens[row] = column of that row's queen
    cols = [False] * n
    diags = [False] * (2 * n - 1)  # Indexed by row - col + n - 1.
    anti_diags = [False] * (2 * n - 1)  # Indexed by row + col.

    def backtrack(row: int) -> None:
        if row == n:
            result.append(["." * col + "Q" + "." * (n - col - 1) for col in queens])
            return
        for col in range(n):
            d = row - col + n - 1
            a = row + col
            if cols[col] or diags[d] or anti_diags[a]:
                continue  # Attacked: prune this branch.
            queens[row] = col  # Choose: put this row's queen in col.
            cols[col] = diags[d] = anti_diags[a] = True
            backtrack(row + 1)  # Explore the next row (one queen per row).
            # Un-choose. The next choice overwrites queens[row], so only the flags need resetting.
            cols[col] = diags[d] = anti_diags[a] = False

    backtrack(0)
    return result


if __name__ == "__main__":
    boards = solve_n_queens(4)
    print(len(boards))  # 2
    for row in boards[0]:
        print(row)  # .Q.. then ...Q then Q... then ..Q.
    print(len(solve_n_queens(8)))  # 92

// Every way to place n queens on an n x n board so no two attack each other.
// Each board is a list of rows, with "Q" for a queen and "." for an empty square.
export function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const queens = new Array<number>(n).fill(0); // queens[row] = column of that row's queen
  const cols = new Array<boolean>(n).fill(false);
  const diags = new Array<boolean>(2 * n - 1).fill(false); // Indexed by row - col + n - 1.
  const antiDiags = new Array<boolean>(2 * n - 1).fill(false); // Indexed by row + col.

  function backtrack(row: number): void {
    if (row === n) {
      result.push(queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1)));
      return;
    }
    for (let col = 0; col < n; col++) {
      const d = row - col + n - 1;
      const a = row + col;
      if (cols[col] || diags[d] || antiDiags[a]) continue; // Attacked: prune this branch.
      queens[row] = col; // Choose: put this row's queen in col.
      cols[col] = diags[d] = antiDiags[a] = true;
      backtrack(row + 1); // Explore the next row (one queen per row).
      // Un-choose. The next choice overwrites queens[row], so only the flags need resetting.
      cols[col] = diags[d] = antiDiags[a] = false;
    }
  }

  backtrack(0);
  return result;
}

const boards = solveNQueens(4);
console.log(boards.length); // 2
for (const row of boards[0]) console.log(row); // .Q.. then ...Q then Q... then ..Q.
console.log(solveNQueens(8).length); // 92

package main

import (
	"fmt"
	"strings"
)

// solveNQueens returns every way to place n queens on an n x n board so no two
// attack each other. Each board is a list of rows, with "Q" for a queen and "."
// for an empty square.
func solveNQueens(n int) [][]string {
	result := [][]string{}
	queens := make([]int, n) // queens[row] = column of that row's queen
	cols := make([]bool, n)
	diags := make([]bool, 2*n-1)     // Indexed by row - col + n - 1.
	antiDiags := make([]bool, 2*n-1) // Indexed by row + col.
	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			board := make([]string, n)
			for r, col := range queens {
				board[r] = strings.Repeat(".", col) + "Q" + strings.Repeat(".", n-col-1)
			}
			result = append(result, board)
			return
		}
		for col := 0; col < n; col++ {
			d := row - col + n - 1
			a := row + col
			if cols[col] || diags[d] || antiDiags[a] {
				continue // Attacked: prune this branch.
			}
			queens[row] = col // Choose: put this row's queen in col.
			cols[col], diags[d], antiDiags[a] = true, true, true
			backtrack(row + 1) // Explore the next row (one queen per row).
			// Un-choose. The next choice overwrites queens[row], so only the flags need resetting.
			cols[col], diags[d], antiDiags[a] = false, false, false
		}
	}
	backtrack(0)
	return result
}

func main() {
	boards := solveNQueens(4)
	fmt.Println(len(boards)) // 2
	for _, row := range boards[0] {
		fmt.Println(row) // .Q.. then ...Q then Q... then ..Q.
	}
	fmt.Println(len(solveNQueens(8))) // 92
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Every way to place n queens on an n x n board so no two attack each other.
    // Each board is a list of rows, with "Q" for a queen and "." for an empty square.
    public static List<List<string>> SolveNQueens(int n)
    {
        var result = new List<List<string>>();
        var queens = new int[n]; // queens[row] = column of that row's queen
        var cols = new bool[n];
        var diags = new bool[2 * n - 1]; // Indexed by row - col + n - 1.
        var antiDiags = new bool[2 * n - 1]; // Indexed by row + col.

        void Backtrack(int row)
        {
            if (row == n)
            {
                result.Add(queens.Select(col => new string('.', col) + "Q" + new string('.', n - col - 1)).ToList());
                return;
            }
            for (int col = 0; col < n; col++)
            {
                int d = row - col + n - 1;
                int a = row + col;
                if (cols[col] || diags[d] || antiDiags[a]) continue; // Attacked: prune this branch.
                queens[row] = col; // Choose: put this row's queen in col.
                cols[col] = diags[d] = antiDiags[a] = true;
                Backtrack(row + 1); // Explore the next row (one queen per row).
                // Un-choose. The next choice overwrites queens[row], so only the flags need resetting.
                cols[col] = diags[d] = antiDiags[a] = false;
            }
        }

        Backtrack(0);
        return result;
    }

    public static void Main()
    {
        var boards = SolveNQueens(4);
        Console.WriteLine(boards.Count); // 2
        foreach (var row in boards[0]) Console.WriteLine(row); // .Q.. then ...Q then Q... then ..Q.
        Console.WriteLine(SolveNQueens(8).Count); // 92
    }
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // Every way to place n queens on an n x n board so no two attack each other.
    // Each board is a list of rows, with "Q" for a queen and "." for an empty square.
    static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queens = new int[n]; // queens[row] = column of that row's queen
        boolean[] cols = new boolean[n];
        boolean[] diags = new boolean[2 * n - 1]; // Indexed by row - col + n - 1.
        boolean[] antiDiags = new boolean[2 * n - 1]; // Indexed by row + col.
        backtrack(0, queens, cols, diags, antiDiags, result);
        return result;
    }

    static void backtrack(int row, int[] queens, boolean[] cols, boolean[] diags,
            boolean[] antiDiags, List<List<String>> result) {
        int n = queens.length;
        if (row == n) {
            List<String> board = new ArrayList<>();
            for (int col : queens) board.add(".".repeat(col) + "Q" + ".".repeat(n - col - 1));
            result.add(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            int d = row - col + n - 1;
            int a = row + col;
            if (cols[col] || diags[d] || antiDiags[a]) continue; // Attacked: prune this branch.
            queens[row] = col; // Choose: put this row's queen in col.
            cols[col] = diags[d] = antiDiags[a] = true;
            backtrack(row + 1, queens, cols, diags, antiDiags, result); // Explore the next row (one queen per row).
            // Un-choose. The next choice overwrites queens[row], so only the flags need resetting.
            cols[col] = diags[d] = antiDiags[a] = false;
        }
    }

    public static void main(String[] args) {
        List<List<String>> boards = solveNQueens(4);
        System.out.println(boards.size()); // 2
        for (String row : boards.get(0)) System.out.println(row); // .Q.. then ...Q then Q... then ..Q.
        System.out.println(solveNQueens(8).size()); // 92
    }
}