1. Sum of All Subsets XOR Total
Easy · LC 1863
Given an integer array, compute the sum of the XOR totals over every one of its 2^n subsets. Recurse with include and exclude branches per element, carrying a running XOR down and adding it to the answer at every leaf. A shortcut worth remembering: each set bit appears in exactly half the subsets, so the answer also equals the OR of all numbers times 2^(n-1).
def subset_xor_sum(nums: list[int]) -> int:
"""LC 1863. Sum of All Subsets XOR Total.
Recurse with an include and an exclude branch per element, carrying
the running XOR down and surrendering it at every leaf -- the 2^n
leaves are exactly the 2^n subsets. Shortcut worth remembering: each
set bit appears in exactly half the subsets, so the answer also
equals (OR of all numbers) * 2^(n-1). O(2^n) time, O(n) stack.
"""
def leaf_totals(i: int, running_xor: int) -> int:
if i == len(nums):
return running_xor # one leaf per subset; its XOR joins the sum
include = leaf_totals(i + 1, running_xor ^ nums[i])
exclude = leaf_totals(i + 1, running_xor)
return include + exclude
return leaf_totals(0, 0)
// LC 1863. Include/exclude recursion per element carries a running XOR down
// the subset tree and adds it to the answer at every leaf, covering all 2^n
// subsets. (Shortcut worth remembering: each set bit appears in exactly half
// the subsets, so the answer also equals (OR of all numbers) * 2^(n-1).)
int subsetXORSum(vector<int> nums) {
int n = static_cast<int>(nums.size());
auto dfs = [&](auto&& self, int i, int acc) -> int {
if (i == n) return acc;
return self(self, i + 1, acc ^ nums[i]) + self(self, i + 1, acc);
};
return dfs(dfs, 0, 0);
}
/// LC 1863. No enumeration needed: toggling any one element that carries a
/// given bit pairs up the 2^n subsets so the bit lands in exactly half of the
/// XOR totals. Every present bit therefore contributes value * 2^(n-1), and
/// the sum collapses to (OR of all numbers) << (n - 1).
pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
nums.iter().fold(0, |acc, &x| acc | x) << (nums.len() - 1)
}
/** LC 1863. Include/exclude per element carrying the running XOR; leaves sum it. (Shortcut: OR of all << (n-1).) */
export function subsetXORSum(nums: number[]): number {
function total(i: number, xor: number): number {
if (i === nums.length) return xor; // one leaf per subset
return total(i + 1, xor ^ nums[i]) + total(i + 1, xor);
}
return total(0, 0);
}
// LC 1863. Include/exclude branch per element carries a running XOR down the
// subset tree; the 2^n leaves are exactly the 2^n subsets, each adding its XOR.
func subsetXORSum(nums []int) int {
var dfs func(i, acc int) int
dfs = func(i, acc int) int {
if i == len(nums) {
return acc
}
return dfs(i+1, acc^nums[i]) + dfs(i+1, acc)
}
return dfs(0, 0)
}
// LC 1863. Include/exclude branch per element; the running XOR rides down and
// every leaf of the 2^n-leaf subset tree surrenders it to the sum.
func subsetXORSum(_ nums: [Int]) -> Int {
func leafTotals(_ i: Int, _ acc: Int) -> Int {
if i == nums.count { return acc }
return leafTotals(i + 1, acc ^ nums[i]) + leafTotals(i + 1, acc)
}
return leafTotals(0, 0)
}
2. Subsets
Medium · LC 78
Given an array of distinct integers, return every possible subset, the full power set, in any order. Backtrack with a start index, recording the current path at every node, then looping i from start onward, appending nums[i], recursing with i+1, and popping to undo. The start index is the invariant: only elements after the last chosen one are eligible, which stops the same subset appearing in two different orders.
def subsets(nums: list[int]) -> list[list[int]]:
"""LC 78. Subsets.
Walk the indices with a binary include/exclude branch at each one,
recording the path once the index runs off the end. Carrying the
start index forward is the invariant that stops the same subset
being built in two different orders. O(n * 2^n) time (the size of
the output), O(n) stack.
"""
power_set: list[list[int]] = []
chosen_path: list[int] = []
def extend(start: int) -> None:
if start == len(nums):
power_set.append(chosen_path[:])
return
chosen_path.append(nums[start]) # branch 1: include nums[start]
extend(start + 1)
chosen_path.pop()
extend(start + 1) # branch 2: exclude it
extend(0)
return power_set
// LC 78. Backtrack with a start index, recording the current path at EVERY
// node of the tree: loop i from start onward, append nums[i], recurse with
// i+1, pop to undo. The start index is the invariant -- only elements after
// the last chosen one are eligible -- which stops the same subset appearing
// in two different orders.
vector<vector<int>> subsets(vector<int> nums) {
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](auto&& self, int start) -> void {
ans.push_back(path);
for (int i = start; i < static_cast<int>(nums.size()); ++i) {
path.push_back(nums[i]);
self(self, i + 1);
path.pop_back();
}
};
dfs(dfs, 0);
return ans;
}
/// LC 78. Start-index backtracking that records the path at EVERY node, not
/// just the leaves. The start index is the invariant: only elements after the
/// last chosen one are eligible, so no subset appears in two orders.
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
fn dfs(nums: &[i32], start: usize, path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
ans.push(path.clone());
for i in start..nums.len() {
path.push(nums[i]);
dfs(nums, i + 1, path, ans);
path.pop();
}
}
let mut ans = Vec::new();
dfs(&nums, 0, &mut Vec::new(), &mut ans);
ans
}
/** LC 78. Start-index backtracking; record the path at EVERY node so one order per subset appears. */
export function subsets(nums: number[]): number[][] {
const ans: number[][] = [];
const path: number[] = [];
function extend(start: number): void {
ans.push([...path]); // every node of the tree is a subset, not only leaves
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
extend(i + 1); // only elements after the last pick are eligible
path.pop();
}
}
extend(0);
return ans;
}
// LC 78. Backtrack with a start index, recording the path at EVERY node of the
// tree; the start invariant stops the same subset being built in two orders.
func subsets(nums []int) [][]int {
ans := [][]int{}
path := []int{}
var dfs func(start int)
dfs = func(start int) {
ans = append(ans, append([]int{}, path...))
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}
// LC 78. Choose, recurse, undo; record every node of the decision tree. The
// start index is the invariant that stops one subset appearing in two orders.
func subsets(_ nums: [Int]) -> [[Int]] {
var ans: [[Int]] = []
var path: [Int] = []
func extend(_ start: Int) {
ans.append(path) // every node is a subset, not just leaves
for i in start..<nums.count {
path.append(nums[i])
extend(i + 1)
path.removeLast()
}
}
extend(0)
return ans
}
3. Combination Sum
Medium · LC 39
Given distinct candidate numbers and a target, return all unique combinations that sum to the target, where each candidate may be reused unlimited times. Backtrack over a start index, subtracting each chosen candidate from the remaining target and pruning the branch when it goes negative. The reuse rule is encoded by recursing with i rather than i+1, which permits the same element again while still preventing permuted duplicates.
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""LC 39. Combination Sum.
Backtrack over a start index, subtracting each chosen candidate from
the remaining target and pruning any branch that overshoots. Reuse
is encoded in one character: recurse with i, not i + 1, so the same
candidate may be picked again while earlier ones stay off limits --
that keeps permuted duplicates out. O(n^(target/min)) branches in
the worst case, O(target/min) stack.
"""
combos: list[list[int]] = []
chosen_path: list[int] = []
def extend(start: int, remaining_target: int) -> None:
if remaining_target == 0:
combos.append(chosen_path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining_target:
continue # overshoot: positive candidates can never recover
chosen_path.append(candidates[i])
extend(i, remaining_target - candidates[i]) # i, not i+1: reuse allowed
chosen_path.pop()
extend(0, target)
return combos
// LC 39. Backtrack over a start index, subtracting each chosen candidate from
// the remaining target and pruning the branch when it would go negative. The
// reuse rule is encoded by recursing with i rather than i+1, which permits
// the same element again while still preventing permuted duplicates.
vector<vector<int>> combinationSum(vector<int> candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](auto&& self, int start, int remaining) -> void {
if (remaining == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < static_cast<int>(candidates.size()); ++i) {
if (candidates[i] > remaining) continue; // prune negative branches
path.push_back(candidates[i]);
self(self, i, remaining - candidates[i]); // i again: reuse allowed
path.pop_back();
}
};
dfs(dfs, 0, target);
return ans;
}
/// LC 39. Subtract each candidate from the remaining target, pruning branches
/// that overshoot. Recursing with i (not i + 1) encodes unlimited reuse while
/// the start index still blocks permuted duplicates.
pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
fn dfs(c: &[i32], start: usize, remaining: i32, path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if remaining == 0 {
ans.push(path.clone());
return;
}
for i in start..c.len() {
if c[i] > remaining {
continue;
}
path.push(c[i]);
dfs(c, i, remaining - c[i], path, ans); // i again: reuse allowed
path.pop();
}
}
let mut ans = Vec::new();
dfs(&candidates, 0, target, &mut Vec::new(), &mut ans);
ans
}
/** LC 39. Start-index backtracking on the remaining target; recursing with i (not i+1) encodes reuse. */
export function combinationSum(candidates: number[], target: number): number[][] {
const ans: number[][] = [];
const path: number[] = [];
function search(start: number, remaining: number): void {
if (remaining === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) continue; // prune before the target goes negative
path.push(candidates[i]);
search(i, remaining - candidates[i]); // i again: same element may repeat, permutations may not
path.pop();
}
}
search(0, target);
return ans;
}
// LC 39. Subtract each chosen candidate from the remaining target, pruning
// overshoots; recursing with i, not i+1, allows reuse without permuted dups.
func combinationSum(candidates []int, target int) [][]int {
ans := [][]int{}
path := []int{}
var dfs func(start, remaining int)
dfs = func(start, remaining int) {
if remaining == 0 {
ans = append(ans, append([]int{}, path...))
return
}
for i := start; i < len(candidates); i++ {
if candidates[i] > remaining {
continue // prune negative branches
}
path = append(path, candidates[i])
dfs(i, remaining-candidates[i]) // i again: reuse allowed
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}
// LC 39. Backtrack over a start index, subtracting choices from the remaining
// target; recursing with i, not i + 1, allows reuse but not permuted repeats.
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
var ans: [[Int]] = []
var path: [Int] = []
func extend(_ start: Int, _ remaining: Int) {
if remaining == 0 {
ans.append(path)
return
}
for i in start..<candidates.count {
if candidates[i] > remaining { continue } // prune negative branches
path.append(candidates[i])
extend(i, remaining - candidates[i]) // i again: reuse allowed
path.removeLast()
}
}
extend(0, target)
return ans
}
4. Combination Sum II
Medium · LC 40
Given candidates that may contain duplicates and a target, return all unique combinations summing to the target, with each array element used at most once. Sort the array, backtrack with a start index, and recurse with i+1 since reuse is forbidden. The key guard: skip nums[i] when i is greater than start and it equals nums[i-1], which removes same-depth repeats while still allowing stacked duplicates.
def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
"""LC 40. Combination Sum II.
Sort, then backtrack with a start index, recursing with i + 1 since
each array element may be used once. The guard that makes it work:
skip candidates[i] when i > start and it equals candidates[i - 1],
which kills same-depth repeats (two branches starting with the same
value) while still allowing stacked duplicates like [1, 1, 6].
O(2^n) time worst case, O(n) stack.
"""
candidates.sort() # groups duplicates and lets the loop break early
combos: list[list[int]] = []
chosen_path: list[int] = []
def extend(start: int, remaining_target: int) -> None:
if remaining_target == 0:
combos.append(chosen_path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining_target:
break # sorted ascending: every later candidate overshoots too
if i > start and candidates[i] == candidates[i - 1]:
continue # same-depth duplicate: the twin at i-1 already led here
chosen_path.append(candidates[i])
extend(i + 1, remaining_target - candidates[i])
chosen_path.pop()
extend(0, target)
return combos
// LC 40. Sort, backtrack with a start index, and recurse with i+1 since reuse
// is forbidden. The key guard: skip candidates[i] when i > start and it
// equals candidates[i-1], which removes same-depth repeats while still
// allowing stacked duplicates (the same value chosen at successive depths).
vector<vector<int>> combinationSum2(vector<int> candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](auto&& self, int start, int remaining) -> void {
if (remaining == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < static_cast<int>(candidates.size()); ++i) {
if (i > start && candidates[i] == candidates[i - 1]) continue; // same-depth duplicate
if (candidates[i] > remaining) break; // sorted: the rest are larger too
path.push_back(candidates[i]);
self(self, i + 1, remaining - candidates[i]);
path.pop_back();
}
};
dfs(dfs, 0, target);
return ans;
}
/// LC 40. Sort, recurse with i + 1 (no reuse), and skip nums[i] when
/// i > start and it equals nums[i - 1]: that removes same-depth repeats while
/// stacked duplicates (deeper levels) stay allowed. Sorted order also lets
/// the loop break as soon as a candidate exceeds the remaining target.
pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
fn dfs(c: &[i32], start: usize, remaining: i32, path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if remaining == 0 {
ans.push(path.clone());
return;
}
for i in start..c.len() {
if c[i] > remaining {
break;
}
if i > start && c[i] == c[i - 1] {
continue; // same-depth duplicate skip
}
path.push(c[i]);
dfs(c, i + 1, remaining - c[i], path, ans);
path.pop();
}
}
let mut sorted = candidates;
sorted.sort_unstable();
let mut ans = Vec::new();
dfs(&sorted, 0, target, &mut Vec::new(), &mut ans);
ans
}
/** LC 40. Sort, recurse with i+1, and skip same-depth duplicates (i > start with a twin to the left). */
export function combinationSum2(candidates: number[], target: number): number[][] {
const sorted = [...candidates].sort((a, b) => a - b);
const ans: number[][] = [];
const path: number[] = [];
function search(start: number, remaining: number): void {
if (remaining === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < sorted.length; i++) {
// same depth, same value: stacked duplicates stay legal, sibling repeats do not
if (i > start && sorted[i] === sorted[i - 1]) continue;
if (sorted[i] > remaining) break; // sorted, so every later candidate overshoots too
path.push(sorted[i]);
search(i + 1, remaining - sorted[i]); // each array element used at most once
path.pop();
}
}
search(0, target);
return ans;
}
// LC 40. Sort, recurse with i+1 (no reuse), and skip candidates[i] when
// i > start and it equals candidates[i-1]: kills same-depth duplicates while
// still allowing stacked ones like [1, 1, 6].
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}
path := []int{}
var dfs func(start, remaining int)
dfs = func(start, remaining int) {
if remaining == 0 {
ans = append(ans, append([]int{}, path...))
return
}
for i := start; i < len(candidates); i++ {
if i > start && candidates[i] == candidates[i-1] {
continue // same-depth duplicate
}
if candidates[i] > remaining {
break // sorted: the rest are larger too
}
path = append(path, candidates[i])
dfs(i+1, remaining-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}
// LC 40. Sort, recurse with i + 1, and skip candidates[i] when i > start and
// it equals its left twin: kills same-depth repeats, keeps stacked duplicates.
func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
var candidates = candidates
candidates.sort() // duplicates adjacent; loop can break on overshoot
var ans: [[Int]] = []
var path: [Int] = []
func extend(_ start: Int, _ remaining: Int) {
if remaining == 0 {
ans.append(path)
return
}
for i in start..<candidates.count {
if i > start && candidates[i] == candidates[i - 1] { continue } // same-depth duplicate
if candidates[i] > remaining { break } // sorted: the rest are larger too
path.append(candidates[i])
extend(i + 1, remaining - candidates[i])
path.removeLast()
}
}
extend(0, target)
return ans
}
5. Combinations
Medium · LC 77
Given integers n and k, return all combinations of k numbers chosen from 1 through n. Backtrack with a start value, appending each candidate, recursing from the next number, and popping, recording the path once it reaches length k. The pruning that matters: when the numbers remaining past the current start cannot fill the open slots, cut the branch immediately rather than exploring it.
def combine(n: int, k: int) -> list[list[int]]:
"""LC 77. Combinations.
Backtrack with a start value, appending each number, recursing from
the next one, and popping; record the path at length k. The pruning
that matters lives in the loop bound: once start passes
n - open_slots + 1 there are not enough numbers left to fill the
remaining slots, so those branches are never entered.
O(k * C(n, k)) time, O(k) stack.
"""
combos: list[list[int]] = []
chosen_path: list[int] = []
def extend(start: int) -> None:
if len(chosen_path) == k:
combos.append(chosen_path[:])
return
open_slots = k - len(chosen_path)
# prune: past n - open_slots + 1 the slots exceed the numbers remaining
for number in range(start, n - open_slots + 2):
chosen_path.append(number)
extend(number + 1)
chosen_path.pop()
extend(1)
return combos
// LC 77. Backtrack with a start value, appending each candidate, recursing
// from the next number, and popping; record the path once it reaches length
// k. The pruning that matters: when the numbers remaining past the current
// start cannot fill the open slots, cut the branch immediately.
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](auto&& self, int start) -> void {
if (static_cast<int>(path.size()) == k) {
ans.push_back(path);
return;
}
int slots = k - static_cast<int>(path.size());
for (int i = start; n - i + 1 >= slots; ++i) { // slots-remaining prune
path.push_back(i);
self(self, i + 1);
path.pop_back();
}
};
dfs(dfs, 1);
return ans;
}
/// LC 77. Backtrack over a start value; the slots-remaining prune caps the
/// loop at n - slots + 1, the highest start that still leaves enough numbers
/// to fill the open slots, cutting doomed branches before they begin.
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
fn dfs(start: i32, n: i32, k: i32, path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if path.len() == k as usize {
ans.push(path.clone());
return;
}
let slots = k - path.len() as i32;
for i in start..=n - slots + 1 {
path.push(i);
dfs(i + 1, n, k, path, ans);
path.pop();
}
}
let mut ans = Vec::new();
dfs(1, n, k, &mut Vec::new(), &mut ans);
ans
}
/** LC 77. Start-value backtracking; stop the loop once the numbers left cannot fill the open slots. */
export function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const path: number[] = [];
function extend(start: number): void {
if (path.length === k) {
ans.push([...path]);
return;
}
const need = k - path.length;
for (let i = start; i <= n - need + 1; i++) {
// the loop bound IS the prune: past it, fewer than `need` numbers remain
path.push(i);
extend(i + 1);
path.pop();
}
}
extend(1);
return ans;
}
// LC 77. Append, recurse from the next number, pop; record at length k. The
// loop bound is the prune: cut starts that cannot fill the open slots.
func combine(n, k int) [][]int {
ans := [][]int{}
path := []int{}
var dfs func(start int)
dfs = func(start int) {
if len(path) == k {
ans = append(ans, append([]int{}, path...))
return
}
slots := k - len(path)
for i := start; n-i+1 >= slots; i++ { // slots-remaining prune
path = append(path, i)
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(1)
return ans
}
// LC 77. Backtrack with a start value, recording the path at length k; the
// loop bound cuts any start that cannot fill the remaining open slots.
func combine(_ n: Int, _ k: Int) -> [[Int]] {
var ans: [[Int]] = []
var path: [Int] = []
func extend(_ start: Int) {
if path.count == k {
ans.append(path)
return
}
let slots = k - path.count
var i = start
while n - i + 1 >= slots { // slots-remaining prune
path.append(i)
extend(i + 1)
path.removeLast()
i += 1
}
}
extend(1)
return ans
}
6. Permutations
Medium · LC 46
Given an array of distinct integers, return every possible permutation. Since order matters a start index no longer works; instead keep a used array, and at each depth loop over all elements, choosing any unused one, recursing, then unmarking it. The recursion finishes when the path length reaches n, and the choose, recurse, undo cycle on the used flags is the entire pattern.
def permute(nums: list[int]) -> list[list[int]]:
"""LC 46. Permutations.
Order matters, so a start index no longer works; keep a used array
instead and at every depth loop over ALL elements, choosing any
unused one, recursing, then unmarking it. The path is complete at
length n. Choose, recurse, undo on the used flags is the entire
pattern. O(n * n!) time, O(n) stack.
"""
permutations: list[list[int]] = []
chosen_path: list[int] = []
used = [False] * len(nums)
def extend() -> None:
if len(chosen_path) == len(nums):
permutations.append(chosen_path[:])
return
for i, num in enumerate(nums):
if used[i]:
continue
used[i] = True
chosen_path.append(num)
extend()
chosen_path.pop() # undo in reverse order of choosing
used[i] = False
extend()
return permutations
// LC 46. Order matters, so a start index no longer works: keep a used array,
// and at each depth loop over ALL elements, choosing any unused one,
// recursing, then unmarking it. The recursion finishes when the path length
// reaches n; the choose, recurse, undo cycle on the flags is the pattern.
vector<vector<int>> permute(vector<int> nums) {
int n = static_cast<int>(nums.size());
vector<vector<int>> ans;
vector<int> path;
vector<bool> used(n, false);
auto dfs = [&](auto&& self) -> void {
if (static_cast<int>(path.size()) == n) {
ans.push_back(path);
return;
}
for (int i = 0; i < n; ++i) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
self(self);
path.pop_back();
used[i] = false;
}
};
dfs(dfs);
return ans;
}
/// LC 46. Order matters, so a start index no longer works: keep a used array
/// and at each depth choose any unused element, recurse, then unmark it.
/// Done when the path length reaches n.
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
fn dfs(nums: &[i32], used: &mut [bool], path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if path.len() == nums.len() {
ans.push(path.clone());
return;
}
for i in 0..nums.len() {
if used[i] {
continue;
}
used[i] = true;
path.push(nums[i]);
dfs(nums, used, path, ans);
path.pop();
used[i] = false;
}
}
let mut used = vec![false; nums.len()];
let mut ans = Vec::new();
dfs(&nums, &mut used, &mut Vec::new(), &mut ans);
ans
}
/** LC 46. Order matters, so a start index fails; a used[] array lets each depth pick ANY unused element. */
export function permute(nums: number[]): number[][] {
const ans: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(nums.length).fill(false);
function build(): void {
if (path.length === nums.length) {
ans.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; // choose
path.push(nums[i]);
build(); // recurse
path.pop(); // undo
used[i] = false;
}
}
build();
return ans;
}
// LC 46. Order matters, so used flags replace the start index: at each depth
// choose any unused element, recurse, undo. Record the path at length n.
func permute(nums []int) [][]int {
ans := [][]int{}
path := []int{}
used := make([]bool, len(nums))
var dfs func()
dfs = func() {
if len(path) == len(nums) {
ans = append(ans, append([]int{}, path...))
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
used[i] = true
path = append(path, nums[i])
dfs()
path = path[:len(path)-1]
used[i] = false
}
}
dfs()
return ans
}
// LC 46. Order matters, so used flags replace the start index: at every depth
// loop over ALL elements, choose any unused one, recurse, then unmark it.
func permute(_ nums: [Int]) -> [[Int]] {
var ans: [[Int]] = []
var path: [Int] = []
var used = [Bool](repeating: false, count: nums.count)
func extend() {
if path.count == nums.count {
ans.append(path)
return
}
for i in 0..<nums.count {
if used[i] { continue }
used[i] = true
path.append(nums[i])
extend()
path.removeLast() // undo in reverse order of choosing
used[i] = false
}
}
extend()
return ans
}
7. Subsets II
Medium · LC 90
Given an integer array that may contain duplicates, return all unique subsets. Sort first, then run the standard subset backtracking with a start index, recording the path at every node of the tree. The duplicate skip mirrors Combination Sum II: when i is greater than start and nums[i] equals nums[i-1], continue past it, so each value extends a given path only once per depth.
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
"""LC 90. Subsets II.
Sort first so equal values sit adjacent, then run subset
backtracking with a start index, recording the path at EVERY node of
the tree rather than only at leaves. The duplicate skip mirrors
Combination Sum II: when i > start and nums[i] equals nums[i - 1],
move on, so each value extends a given path once per depth.
O(n * 2^n) time, O(n) stack.
"""
nums.sort() # duplicates must be adjacent for the skip to see them
power_set: list[list[int]] = []
chosen_path: list[int] = []
def extend(start: int) -> None:
power_set.append(chosen_path[:]) # every node is a subset, not just leaves
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # same-depth duplicate: the twin at i-1 built this subtree
chosen_path.append(nums[i])
extend(i + 1)
chosen_path.pop()
extend(0)
return power_set
// LC 90. Sort first, then run the standard subset backtracking, recording the
// path at every node. The duplicate skip mirrors Combination Sum II: when
// i > start and nums[i] equals nums[i-1], continue past it, so each value
// extends a given path only once per depth.
vector<vector<int>> subsetsWithDup(vector<int> nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](auto&& self, int start) -> void {
ans.push_back(path);
for (int i = start; i < static_cast<int>(nums.size()); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue; // same-depth duplicate
path.push_back(nums[i]);
self(self, i + 1);
path.pop_back();
}
};
dfs(dfs, 0);
return ans;
}
/// LC 90. Sort first, then run the LC 78 walk recording every node; the
/// LC 40 guard (i > start and nums[i] == nums[i - 1]) means each value
/// extends a given path only once per depth.
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
fn dfs(nums: &[i32], start: usize, path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
ans.push(path.clone());
for i in start..nums.len() {
if i > start && nums[i] == nums[i - 1] {
continue; // same-depth duplicate skip
}
path.push(nums[i]);
dfs(nums, i + 1, path, ans);
path.pop();
}
}
let mut sorted = nums;
sorted.sort_unstable();
let mut ans = Vec::new();
dfs(&sorted, 0, &mut Vec::new(), &mut ans);
ans
}
/** LC 90. Subsets backtracking after sorting, with the LC 40 same-depth duplicate skip. */
export function subsetsWithDup(nums: number[]): number[][] {
const sorted = [...nums].sort((a, b) => a - b);
const ans: number[][] = [];
const path: number[] = [];
function extend(start: number): void {
ans.push([...path]);
for (let i = start; i < sorted.length; i++) {
if (i > start && sorted[i] === sorted[i - 1]) continue; // each value extends a path once per depth
path.push(sorted[i]);
extend(i + 1);
path.pop();
}
}
extend(0);
return ans;
}
// LC 90. Sort, record every node as in subsets, and skip nums[i] when i > start
// and it equals nums[i-1], so each value extends a given path once per depth.
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
ans := [][]int{}
path := []int{}
var dfs func(start int)
dfs = func(start int) {
ans = append(ans, append([]int{}, path...))
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue // same-depth duplicate
}
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}
// LC 90. Sorted subset backtracking recording every node, plus the same-depth
// duplicate skip: each value extends a given path only once per depth.
func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
var nums = nums
nums.sort() // duplicates must be adjacent for the skip to see them
var ans: [[Int]] = []
var path: [Int] = []
func extend(_ start: Int) {
ans.append(path)
for i in start..<nums.count {
if i > start && nums[i] == nums[i - 1] { continue } // same-depth duplicate
path.append(nums[i])
extend(i + 1)
path.removeLast()
}
}
extend(0)
return ans
}
8. Permutations II
Medium · LC 47
Given an array that may contain duplicates, return all unique permutations. Sort the array and backtrack with a used array as in regular permutations, choosing any unused element at each depth. The duplicate rule: skip nums[i] when it equals nums[i-1] and nums[i-1] is not currently used, which forces equal values to be placed left to right and eliminates mirrored branches.
def permute_unique(nums: list[int]) -> list[list[int]]:
"""LC 47. Permutations II.
Sort, then permute with used flags as in LC 46, plus one guard: skip
nums[i] when it equals nums[i - 1] and nums[i - 1] is NOT currently
used. That forces equal values into the path left to right, so of
the k! interchangeable orderings of k equal values exactly one
survives. O(n * n!) worst-case time, O(n) stack.
"""
nums.sort() # equal values must be adjacent for the twin check
permutations: list[list[int]] = []
chosen_path: list[int] = []
used = [False] * len(nums)
def extend() -> None:
if len(chosen_path) == len(nums):
permutations.append(chosen_path[:])
return
for i, num in enumerate(nums):
if used[i]:
continue
# WHY "not used[i - 1]": if the equal twin to the left is still
# free, the twin was popped at this very depth a moment ago, so
# choosing nums[i] now would replay the twin's whole subtree with
# identical values. If the twin IS used, it sits earlier in the
# current path and this placement is genuinely new.
if i > 0 and num == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
chosen_path.append(num)
extend()
chosen_path.pop()
used[i] = False
extend()
return permutations
// LC 47. Sort and backtrack with a used array as in regular permutations. The
// twin-used rule: skip nums[i] when it equals nums[i-1] and nums[i-1] is NOT
// currently used, which forces equal values to be placed left to right and
// eliminates mirrored branches.
vector<vector<int>> permuteUnique(vector<int> nums) {
sort(nums.begin(), nums.end());
int n = static_cast<int>(nums.size());
vector<vector<int>> ans;
vector<int> path;
vector<bool> used(n, false);
auto dfs = [&](auto&& self) -> void {
if (static_cast<int>(path.size()) == n) {
ans.push_back(path);
return;
}
for (int i = 0; i < n; ++i) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // twin-used rule
used[i] = true;
path.push_back(nums[i]);
self(self);
path.pop_back();
used[i] = false;
}
};
dfs(dfs);
return ans;
}
/// LC 47. Sort, then permute with a used array plus the twin-used rule:
/// skip nums[i] when it equals nums[i - 1] and that left twin is NOT used.
pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
fn dfs(nums: &[i32], used: &mut [bool], path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if path.len() == nums.len() {
ans.push(path.clone());
return;
}
for i in 0..nums.len() {
if used[i] {
continue;
}
// WHY the twin-used rule works: an unused left twin means some
// shallower frame already had the chance to place that identical
// value here and its branch produced (or will produce) exactly
// this permutation. Skipping forces equal values to be consumed
// strictly left to right, so each distinct arrangement is built
// by exactly one branch instead of one per twin ordering.
if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
continue;
}
used[i] = true;
path.push(nums[i]);
dfs(nums, used, path, ans);
path.pop();
used[i] = false;
}
}
let mut sorted = nums;
sorted.sort_unstable();
let mut used = vec![false; sorted.len()];
let mut ans = Vec::new();
dfs(&sorted, &mut used, &mut Vec::new(), &mut ans);
ans
}
/** LC 47. Sort + used[] permutations, skipping a value whose identical left twin is not in the path. */
export function permuteUnique(nums: number[]): number[][] {
const sorted = [...nums].sort((a, b) => a - b);
const ans: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(sorted.length).fill(false);
function build(): void {
if (path.length === sorted.length) {
ans.push([...path]);
return;
}
for (let i = 0; i < sorted.length; i++) {
if (used[i]) continue;
// WHY the twin-used rule works: an unused left twin means some sibling
// branch picks that twin here instead and then plays out identically,
// since equal values are interchangeable. Forcing equal values into the
// path strictly left to right keeps exactly one of those mirrored
// branches and discards the rest.
if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;
used[i] = true;
path.push(sorted[i]);
build();
path.pop();
used[i] = false;
}
}
build();
return ans;
}
// LC 47. Sort and permute with used flags, plus the twin-used rule: skip
// nums[i] when it equals nums[i-1] and nums[i-1] is NOT used, forcing equal
// values into the path left to right.
func permuteUnique(nums []int) [][]int {
sort.Ints(nums)
ans := [][]int{}
path := []int{}
used := make([]bool, len(nums))
var dfs func()
dfs = func() {
if len(path) == len(nums) {
ans = append(ans, append([]int{}, path...))
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue // twin-used rule
}
used[i] = true
path = append(path, nums[i])
dfs()
path = path[:len(path)-1]
used[i] = false
}
}
dfs()
return ans
}
// LC 47. Sort, then permute with used flags; skip nums[i] when its equal twin
// at i - 1 is NOT used, so duplicates are only ever placed left to right.
func permuteUnique(_ nums: [Int]) -> [[Int]] {
var nums = nums
nums.sort() // equal values must be adjacent for the twin check
var ans: [[Int]] = []
var path: [Int] = []
var used = [Bool](repeating: false, count: nums.count)
func extend() {
if path.count == nums.count {
ans.append(path)
return
}
for i in 0..<nums.count {
if used[i] { continue }
if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] { continue } // twin-used rule
used[i] = true
path.append(nums[i])
extend()
path.removeLast()
used[i] = false
}
}
extend()
return ans
}
9. Generate Parentheses
Medium · LC 22
Given n, return all strings of n pairs of parentheses that are well formed. Build the string one character at a time, recursing on two choices: add an open parenthesis while open is below n, and add a close parenthesis while close is below open. Those gates are the whole validity proof, since no prefix ever closes more than it opens, and recursion stops at length 2n.
def generate_parenthesis(n: int) -> list[str]:
"""LC 22. Generate Parentheses.
Build the string one character at a time with two gated choices: add
'(' while open_count < n, add ')' while close_count < open_count.
Those gates ARE the validity proof -- no prefix ever closes more
than it opens, and every branch reaching length 2n is balanced.
O(4^n / sqrt(n)) output (the Catalan number), O(n) stack.
"""
well_formed: list[str] = []
chosen_chars: list[str] = []
def extend(open_count: int, close_count: int) -> None:
if len(chosen_chars) == 2 * n:
well_formed.append("".join(chosen_chars))
return
if open_count < n: # gate 1: still have '(' left to spend
chosen_chars.append("(")
extend(open_count + 1, close_count)
chosen_chars.pop()
if close_count < open_count: # gate 2: never close what isn't open
chosen_chars.append(")")
extend(open_count, close_count + 1)
chosen_chars.pop()
extend(0, 0)
return well_formed
// LC 22. Build the string one character at a time with two gated choices: add
// '(' while open < n, add ')' while close < open. Those gates are the whole
// validity proof -- no prefix ever closes more than it opens -- and the
// recursion stops at length 2n.
vector<string> generateParenthesis(int n) {
vector<string> ans;
string cur;
auto dfs = [&](auto&& self, int open, int close) -> void {
if (static_cast<int>(cur.size()) == 2 * n) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
self(self, open + 1, close);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
self(self, open, close + 1);
cur.pop_back();
}
};
dfs(dfs, 0, 0);
return ans;
}
/// LC 22. Two gated choices per step: '(' while open < n, ')' while
/// close < open. The gates are the whole validity proof -- no prefix ever
/// closes more than it opens -- and recursion stops at n closes (length 2n).
pub fn generate_parenthesis(n: i32) -> Vec<String> {
fn dfs(open: i32, close: i32, n: i32, buf: &mut String, ans: &mut Vec<String>) {
if close == n {
ans.push(buf.clone());
return;
}
if open < n {
buf.push('(');
dfs(open + 1, close, n, buf, ans);
buf.pop();
}
if close < open {
buf.push(')');
dfs(open, close + 1, n, buf, ans);
buf.pop();
}
}
let mut ans = Vec::new();
dfs(0, 0, n, &mut String::new(), &mut ans);
ans
}
/** LC 22. Two gated choices per step: '(' while open < n, ')' while close < open; the gates ARE the proof. */
export function generateParenthesis(n: number): string[] {
const ans: string[] = [];
const path: string[] = [];
function build(open: number, close: number): void {
if (path.length === 2 * n) {
ans.push(path.join(""));
return;
}
if (open < n) {
path.push("(");
build(open + 1, close);
path.pop();
}
if (close < open) {
// no prefix ever closes more than it opens, so every finished string is valid
path.push(")");
build(open, close + 1);
path.pop();
}
}
build(0, 0);
return ans;
}
// LC 22. Two gated choices: add '(' while open < n, add ')' while close < open.
// The gates are the validity proof; every branch reaching length 2n is balanced.
func generateParenthesis(n int) []string {
ans := []string{}
cur := []byte{}
var dfs func(open, close int)
dfs = func(open, close int) {
if len(cur) == 2*n {
ans = append(ans, string(cur))
return
}
if open < n {
cur = append(cur, '(')
dfs(open+1, close)
cur = cur[:len(cur)-1]
}
if close < open {
cur = append(cur, ')')
dfs(open, close+1)
cur = cur[:len(cur)-1]
}
}
dfs(0, 0)
return ans
}
// LC 22. Two gated choices per character: '(' while openCount < n, ')' while
// closeCount < openCount. The gates ARE the validity proof.
func generateParenthesis(_ n: Int) -> [String] {
var ans: [String] = []
var cur = ""
func extend(_ openCount: Int, _ closeCount: Int) {
if cur.count == 2 * n {
ans.append(cur)
return
}
if openCount < n { // gate 1: still have '(' left to spend
cur.append("(")
extend(openCount + 1, closeCount)
cur.removeLast()
}
if closeCount < openCount { // gate 2: never close what isn't open
cur.append(")")
extend(openCount, closeCount + 1)
cur.removeLast()
}
}
extend(0, 0)
return ans
}
10. Word Search
Medium · LC 79
Given a 2D board of letters and a word, decide whether the word can be traced through horizontally or vertically adjacent cells without reusing a cell. From every cell matching the first letter, run a DFS that advances one character per step into the four neighbors. Mark the current cell with a sentinel before recursing and restore it afterward; that undo step is what lets other paths reuse the cell.
def exist(board: list[list[str]], word: str) -> bool:
"""LC 79. Word Search -- DFS plus undo, i.e. backtracking.
The mark is temporary: overwrite the cell with '#' so the current
path cannot reuse it, then RESTORE it before returning so sibling
paths can. Permanent marking is the classic wrong answer here.
O(mn * 3^L) time (3 because we never go back where we came from),
O(L) stack.
"""
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
saved, board[r][c] = board[r][c], "#"
found = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = saved
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
static bool wordDfs(vector<vector<char>>& board, const string& word, int r, int c, size_t i) {
if (i == word.size()) return true;
int rows = static_cast<int>(board.size()), cols = static_cast<int>(board[0].size());
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i]) return false;
char saved = board[r][c];
board[r][c] = '#';
bool found = wordDfs(board, word, r + 1, c, i + 1) || wordDfs(board, word, r - 1, c, i + 1) ||
wordDfs(board, word, r, c + 1, i + 1) || wordDfs(board, word, r, c - 1, i + 1);
board[r][c] = saved;
return found;
}
bool exist(vector<vector<char>> board, string word) {
for (int r = 0; r < static_cast<int>(board.size()); ++r)
for (int c = 0; c < static_cast<int>(board[0].size()); ++c)
if (wordDfs(board, word, r, c, 0)) return true;
return false;
}
/// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
let word: Vec<char> = word.chars().collect();
fn dfs(board: &mut Vec<Vec<char>>, word: &[char], r: usize, c: usize, i: usize) -> bool {
if i == word.len() {
return true;
}
if r >= board.len() || c >= board[0].len() || board[r][c] != word[i] {
return false;
}
let saved = board[r][c];
board[r][c] = '#';
let found = dfs(board, word, r + 1, c, i + 1)
|| dfs(board, word, r.wrapping_sub(1), c, i + 1)
|| dfs(board, word, r, c + 1, i + 1)
|| dfs(board, word, r, c.wrapping_sub(1), i + 1);
board[r][c] = saved;
found
}
for r in 0..board.len() {
for c in 0..board[0].len() {
if dfs(&mut board, &word, r, c, 0) {
return true;
}
}
}
false
}
/** LC 79. DFS + undo = backtracking: mark '#', recurse, restore. */
export function exist(board: string[][], word: string): boolean {
const rows = board.length;
const cols = board[0].length;
function dfs(r: number, c: number, i: number): boolean {
if (i === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
const saved = 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] = saved;
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
func exist(board [][]byte, word string) bool {
rows, cols := len(board), len(board[0])
var dfs func(r, c, i int) bool
dfs = func(r, c, i int) bool {
if i == len(word) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i] {
return false
}
saved := board[r][c]
board[r][c] = '#'
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] = saved
return found
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
func exist(_ board: [[Character]], _ word: String) -> Bool {
var board = board
let rows = board.count, cols = board[0].count
let target = Array(word)
func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
if i == target.count { return true }
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != target[i] { return false }
let saved = board[r][c]
board[r][c] = "#"
let 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] = saved
return found
}
for r in 0..<rows {
for c in 0..<cols {
if dfs(r, c, 0) { return true }
}
}
return false
}
11. Palindrome Partitioning
Medium · LC 131
Given a string s, return all ways to partition it into substrings that are each palindromes. Backtrack on the cut position: from the current start, try each end whose substring is a palindrome, append it, recurse from end+1, then pop. The real choice is where to cut, and checking the palindrome before recursing prunes whole subtrees; a precomputed table makes each check O(1).
def partition(s: str) -> list[list[str]]:
"""LC 131. Palindrome Partitioning.
The real choice is where to cut: from the current start, try every
end whose substring is a palindrome, append that piece, recurse from
end + 1, then pop. Checking the palindrome BEFORE recursing prunes
whole subtrees; a precomputed table would make each check O(1), but
the two-pointer scan below is accepted. O(n * 2^n) time, O(n) stack.
"""
partitions: list[list[str]] = []
chosen_pieces: list[str] = []
def is_palindrome(lo: int, hi: int) -> bool:
while lo < hi:
if s[lo] != s[hi]:
return False
lo += 1
hi -= 1
return True
def extend(start: int) -> None:
if start == len(s):
partitions.append(chosen_pieces[:])
return
for end in range(start, len(s)):
if not is_palindrome(start, end):
continue # prune: a non-palindrome piece can never be fixed later
chosen_pieces.append(s[start : end + 1])
extend(end + 1)
chosen_pieces.pop()
extend(0)
return partitions
// LC 131. Backtrack on the cut position: from the current start, try each end
// whose substring is a palindrome, append it, recurse from end+1, then pop.
// The real choice is where to cut, and checking the palindrome BEFORE
// recursing prunes whole subtrees (a precomputed table would make each check
// O(1); the two-pointer check below keeps it simple).
vector<vector<string>> partition(string s) {
int n = static_cast<int>(s.size());
vector<vector<string>> ans;
vector<string> path;
auto isPalindrome = [&](int lo, int hi) -> bool {
while (lo < hi)
if (s[lo++] != s[hi--]) return false;
return true;
};
auto dfs = [&](auto&& self, int start) -> void {
if (start == n) {
ans.push_back(path);
return;
}
for (int end = start; end < n; ++end) {
if (!isPalindrome(start, end)) continue; // palindrome prune
path.push_back(s.substr(start, end - start + 1));
self(self, end + 1);
path.pop_back();
}
};
dfs(dfs, 0);
return ans;
}
/// LC 131. The real choice is where to cut: from the current start try each
/// end whose byte slice is a palindrome, recurse from end, then pop. Checking
/// the palindrome BEFORE recursing prunes whole subtrees of doomed cuts.
pub fn partition(s: String) -> Vec<Vec<String>> {
fn is_pal(b: &[u8]) -> bool {
let (mut i, mut j) = (0, b.len() - 1);
while i < j {
if b[i] != b[j] {
return false;
}
i += 1;
j -= 1;
}
true
}
fn dfs(s: &str, start: usize, path: &mut Vec<String>, ans: &mut Vec<Vec<String>>) {
if start == s.len() {
ans.push(path.clone());
return;
}
for end in start + 1..=s.len() {
if is_pal(&s.as_bytes()[start..end]) {
path.push(s[start..end].to_string());
dfs(s, end, path, ans);
path.pop();
}
}
}
let mut ans = Vec::new();
dfs(&s, 0, &mut Vec::new(), &mut ans);
ans
}
/** LC 131. Backtrack on the cut position; an O(1) precomputed palindrome table prunes before recursing. */
export function partition(s: string): string[][] {
const n = s.length;
// isPal[i][j] built shortest-first so the inner slice is always ready
const isPal: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
isPal[i][j] = s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1]);
}
}
const ans: string[][] = [];
const path: string[] = [];
function cut(start: number): void {
if (start === n) {
ans.push([...path]);
return;
}
for (let end = start; end < n; end++) {
if (!isPal[start][end]) continue; // a non-palindrome piece kills the whole subtree
path.push(s.slice(start, end + 1));
cut(end + 1);
path.pop();
}
}
cut(0);
return ans;
}
// LC 131. Choose the cut point: try every end whose piece is a palindrome,
// recurse from end+1, pop. Checking BEFORE recursing prunes whole subtrees.
func partition(s string) [][]string {
ans := [][]string{}
path := []string{}
isPalindrome := func(lo, hi int) bool {
for lo < hi {
if s[lo] != s[hi] {
return false
}
lo++
hi--
}
return true
}
var dfs func(start int)
dfs = func(start int) {
if start == len(s) {
ans = append(ans, append([]string{}, path...))
return
}
for end := start; end < len(s); end++ {
if !isPalindrome(start, end) {
continue // palindrome prune
}
path = append(path, s[start:end+1])
dfs(end + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}
// LC 131. The real choice is where to cut: append every palindromic piece
// from start, recurse past it, pop. Checking the palindrome BEFORE recursing
// prunes whole subtrees.
func partition(_ s: String) -> [[String]] {
let chars = Array(s)
let n = chars.count
var ans: [[String]] = []
var path: [String] = []
func isPalindrome(_ lo: Int, _ hi: Int) -> Bool {
var lo = lo, hi = hi
while lo < hi {
if chars[lo] != chars[hi] { return false }
lo += 1
hi -= 1
}
return true
}
func extend(_ start: Int) {
if start == n {
ans.append(path)
return
}
for end in start..<n {
if !isPalindrome(start, end) { continue } // palindrome prune
path.append(String(chars[start...end]))
extend(end + 1)
path.removeLast()
}
}
extend(0)
return ans
}
12. Letter Combinations of a Phone Number
Medium · LC 17
Given a string of digits 2 through 9, return all letter strings those digits could represent on a phone keypad. Map each digit to its letters, then DFS one digit position at a time, appending each candidate letter, recursing to the next digit, and removing it. This is a plain cartesian product over the letter groups; the one trap is returning an empty list rather than a single empty string for empty input.
def letter_combinations(digits: str) -> list[str]:
"""LC 17. Letter Combinations of a Phone Number.
Map each digit to its keypad letters, then DFS one digit position at
a time: append a candidate letter, recurse to the next digit, remove
it. A plain cartesian product over the letter groups; the one trap
is returning [] rather than [""] for empty input. O(n * 4^n) time,
O(n) stack.
"""
if not digits:
return [] # the trap: empty input yields NO combinations, not one empty one
keypad = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
combos: list[str] = []
chosen_letters: list[str] = []
def extend(i: int) -> None:
if i == len(digits):
combos.append("".join(chosen_letters))
return
for letter in keypad[digits[i]]:
chosen_letters.append(letter)
extend(i + 1)
chosen_letters.pop()
extend(0)
return combos
// LC 17. Plain cartesian product over the keypad letter groups: DFS one digit
// position at a time, appending each candidate letter, recursing to the next
// digit, and removing it. The one trap is returning an empty LIST rather than
// a single empty string for empty input.
vector<string> letterCombinations(string digits) {
vector<string> ans;
if (digits.empty()) return ans;
const vector<string> keypad = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
string cur;
auto dfs = [&](auto&& self, int i) -> void {
if (i == static_cast<int>(digits.size())) {
ans.push_back(cur);
return;
}
for (char c : keypad[digits[i] - '0']) {
cur.push_back(c);
self(self, i + 1);
cur.pop_back();
}
};
dfs(dfs, 0);
return ans;
}
/// LC 17. Plain cartesian product over the keypad letter groups, one digit
/// position per depth. The one trap: empty input returns an empty list, not
/// a list holding the empty string.
pub fn letter_combinations(digits: String) -> Vec<String> {
fn dfs(digits: &[u8], pos: usize, buf: &mut String, ans: &mut Vec<String>) {
const KEYPAD: [&str; 8] = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
if pos == digits.len() {
ans.push(buf.clone());
return;
}
for ch in KEYPAD[(digits[pos] - b'2') as usize].chars() {
buf.push(ch);
dfs(digits, pos + 1, buf, ans);
buf.pop();
}
}
if digits.is_empty() {
return Vec::new();
}
let mut ans = Vec::new();
dfs(digits.as_bytes(), 0, &mut String::new(), &mut ans);
ans
}
/** LC 17. Cartesian product over keypad letter groups, one digit position per depth. */
export function letterCombinations(digits: string): string[] {
if (digits.length === 0) return []; // empty LIST, not [""]
const keypad: Record<string, string> = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
};
const ans: string[] = [];
const path: string[] = [];
function build(index: number): void {
if (index === digits.length) {
ans.push(path.join(""));
return;
}
for (const letter of keypad[digits[index]]) {
path.push(letter);
build(index + 1);
path.pop();
}
}
build(0);
return ans;
}
// LC 17. Cartesian product over the keypad rows: append a letter, recurse to
// the next digit, remove it. Empty input yields an empty LIST, not [""].
func letterCombinations(digits string) []string {
ans := []string{}
if len(digits) == 0 {
return ans
}
keypad := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
cur := []byte{}
var dfs func(i int)
dfs = func(i int) {
if i == len(digits) {
ans = append(ans, string(cur))
return
}
for _, c := range []byte(keypad[digits[i]-'0']) {
cur = append(cur, c)
dfs(i + 1)
cur = cur[:len(cur)-1]
}
}
dfs(0)
return ans
}
// LC 17. Cartesian product over the keypad letter groups, one digit position
// per depth; the trap is returning an empty LIST, not one empty string.
func letterCombinations(_ digits: String) -> [String] {
if digits.isEmpty { return [] }
let keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
let digitChars = Array(digits)
var ans: [String] = []
var cur = ""
func extend(_ i: Int) {
if i == digitChars.count {
ans.append(cur)
return
}
for letter in keypad[digitChars[i].wholeNumberValue!] {
cur.append(letter)
extend(i + 1)
cur.removeLast()
}
}
extend(0)
return ans
}
13. Matchsticks to Square
Medium · LC 473
Given matchstick lengths, decide whether all of them can form a square with every stick used exactly once. First check the total is divisible by 4, then backtrack each stick into one of four side buckets targeting total/4, removing it on failure. Sorting sticks in descending order fails fast, and skipping buckets whose current sum equals an already-tried bucket's sum removes symmetric duplicate work.
def makesquare(matchsticks: list[int]) -> bool:
"""LC 473. Matchsticks to Square.
Check the total is divisible by 4, then backtrack each stick into
one of four side buckets targeting total / 4, removing it on
failure. Sorting descending fails fast: the biggest sticks have the
fewest homes, so doomed branches die near the root instead of after
exponential work. O(4^n) worst case, heavily pruned; O(n) stack.
"""
total = sum(matchsticks)
side, leftover = divmod(total, 4)
if leftover or not matchsticks:
return False
matchsticks.sort(reverse=True) # biggest first: dead ends surface immediately
if matchsticks[0] > side:
return False
buckets = [0, 0, 0, 0]
def place(i: int) -> bool:
if i == len(matchsticks):
return True # nothing overflowed and total == 4 * side, so all sides match
tried_sums = set()
for j in range(4):
if buckets[j] + matchsticks[i] > side:
continue # pruning 1: this stick would overflow the side
if buckets[j] in tried_sums:
continue # pruning 2: equal-sum buckets are interchangeable, so
# this stick already failed an identical bucket -- same subtree
tried_sums.add(buckets[j])
buckets[j] += matchsticks[i]
if place(i + 1):
return True
buckets[j] -= matchsticks[i]
return False
return place(0)
// LC 473. The total must divide by 4; then backtrack each stick into one of
// four side buckets targeting total/4, removing it on failure. Sorting sticks
// in DESCENDING order fails fast, and skipping buckets whose current sum
// equals an already-tried bucket's sum removes symmetric duplicate work.
bool makesquare(vector<int> matchsticks) {
long long total = 0;
for (int stick : matchsticks) total += stick;
if (total % 4 != 0) return false;
long long side = total / 4;
sort(matchsticks.rbegin(), matchsticks.rend()); // descending: fail fast
if (matchsticks[0] > side) return false;
int n = static_cast<int>(matchsticks.size());
vector<long long> sides(4, 0);
auto dfs = [&](auto&& self, int i) -> bool {
if (i == n) return true; // all placed, none over side, total forces equality
for (int b = 0; b < 4; ++b) {
if (sides[b] + matchsticks[i] > side) continue;
bool symmetric = false; // equal-bucket skip: same sum, same subtree
for (int prev = 0; prev < b; ++prev)
if (sides[prev] == sides[b]) {
symmetric = true;
break;
}
if (symmetric) continue;
sides[b] += matchsticks[i];
if (self(self, i + 1)) return true;
sides[b] -= matchsticks[i];
}
return false;
};
return dfs(dfs, 0);
}
/// LC 473. Total must split into 4 sides of total/4; backtrack each stick
/// into one of four buckets, removing it on failure. Sorting descending fails
/// fast (big sticks have the fewest homes), and skipping any bucket whose sum
/// equals an earlier bucket's sum removes symmetric duplicate work.
pub fn makesquare(matchsticks: Vec<i32>) -> bool {
fn dfs(sticks: &[i32], idx: usize, sides: &mut [i32; 4], side: i32) -> bool {
if idx == sticks.len() {
return true; // total == 4 * side, so all four sides are full
}
for b in 0..4 {
if sides[b] + sticks[idx] > side {
continue;
}
if sides[..b].iter().any(|&s| s == sides[b]) {
continue; // equal-bucket skip: same sum, same subtree
}
sides[b] += sticks[idx];
if dfs(sticks, idx + 1, sides, side) {
return true;
}
sides[b] -= sticks[idx];
}
false
}
let total: i32 = matchsticks.iter().sum();
if total % 4 != 0 {
return false;
}
let side = total / 4;
let mut sticks = matchsticks;
sticks.sort_unstable_by(|a, b| b.cmp(a));
if sticks[0] > side {
return false;
}
dfs(&sticks, 0, &mut [0; 4], side)
}
/** LC 473. Drop each stick into one of 4 side buckets; sort descending to fail fast, skip equal buckets. */
export function makesquare(matchsticks: number[]): boolean {
const total = matchsticks.reduce((a, b) => a + b, 0);
if (total % 4 !== 0) return false;
const side = total / 4;
const sticks = [...matchsticks].sort((a, b) => b - a); // big sticks first: bad branches die early
if (sticks[0] > side) return false;
const sides = [0, 0, 0, 0];
function place(index: number): boolean {
if (index === sticks.length) return true; // all placed and none overflows, so all four equal `side`
for (let j = 0; j < 4; j++) {
if (sides[j] + sticks[index] > side) continue;
// an earlier bucket with the SAME sum already failed this stick; retrying is symmetric work
if (sides.indexOf(sides[j]) !== j) continue;
sides[j] += sticks[index];
if (place(index + 1)) return true;
sides[j] -= sticks[index];
}
return false;
}
return place(0);
}
// LC 473. Drop each stick into one of four side buckets targeting total/4;
// sort descending to fail fast and skip equal-sum buckets (same subtree twice).
func makesquare(matchsticks []int) bool {
total := 0
for _, stick := range matchsticks {
total += stick
}
if total%4 != 0 || len(matchsticks) == 0 {
return false
}
side := total / 4
sort.Sort(sort.Reverse(sort.IntSlice(matchsticks))) // descending: fail fast
if matchsticks[0] > side {
return false
}
sides := make([]int, 4)
var dfs func(i int) bool
dfs = func(i int) bool {
if i == len(matchsticks) {
return true // all placed, none over side, total forces equality
}
for b := 0; b < 4; b++ {
if sides[b]+matchsticks[i] > side {
continue
}
symmetric := false // equal-bucket skip: same sum, same subtree
for prev := 0; prev < b; prev++ {
if sides[prev] == sides[b] {
symmetric = true
break
}
}
if symmetric {
continue
}
sides[b] += matchsticks[i]
if dfs(i + 1) {
return true
}
sides[b] -= matchsticks[i]
}
return false
}
return dfs(0)
}
// LC 473. Backtrack each stick into one of 4 side buckets targeting total / 4;
// sort descending to fail fast and skip equal-sum buckets (same subtree).
func makesquare(_ matchsticks: [Int]) -> Bool {
let total = matchsticks.reduce(0, +)
if matchsticks.isEmpty || total % 4 != 0 { return false }
let side = total / 4
var sticks = matchsticks
sticks.sort(by: >) // descending: dead ends surface immediately
if sticks[0] > side { return false }
var sides = [Int](repeating: 0, count: 4)
func place(_ i: Int) -> Bool {
if i == sticks.count { return true } // none overflowed; total forces equality
for b in 0..<4 {
if sides[b] + sticks[i] > side { continue } // pruning 1: overflows the side
if (0..<b).contains(where: { sides[$0] == sides[b] }) { continue } // pruning 2: equal-sum bucket already failed this stick
sides[b] += sticks[i]
if place(i + 1) { return true }
sides[b] -= sticks[i]
}
return false
}
return place(0)
}
14. Partition to K Equal Sum Subsets
Medium · LC 698
Given an integer array and k, decide whether it can be split into k subsets with equal sums. Either backtrack elements into k running buckets as in Matchsticks to Square, or memoize over a bitmask of chosen elements, completing one subset at a time. Pruning carries it: sort descending, skip buckets with equal sums, and when a subset hits the target restart the search for the next one.
def can_partition_k_subsets(nums: list[int], k: int) -> bool:
"""LC 698. Partition to K Equal Sum Subsets.
Matchsticks to Square with k buckets instead of four: backtrack each
number into a bucket targeting total / k. The same two prunings
carry it -- sort descending so big numbers fail fast, and never drop
a number into a bucket whose sum repeats one already tried for that
number, since equal buckets lead to symmetric duplicate subtrees.
O(k^n) worst case, heavily pruned; O(n) stack.
"""
total = sum(nums)
target, leftover = divmod(total, k)
if leftover:
return False
nums.sort(reverse=True) # biggest first: doomed branches die near the root
if nums[0] > target:
return False
buckets = [0] * k
def place(i: int) -> bool:
if i == len(nums):
return True # no bucket exceeds target and they sum to k * target
tried_sums = set()
for j in range(k):
if buckets[j] + nums[i] > target:
continue # pruning 1: overflows this bucket
if buckets[j] in tried_sums:
continue # pruning 2: an equal-sum bucket already failed this number
tried_sums.add(buckets[j])
buckets[j] += nums[i]
if place(i + 1):
return True
buckets[j] -= nums[i]
return False
return place(0)
// LC 698. Matchsticks to Square generalized to k buckets: backtrack each
// element into a running bucket that stays within target = total/k. The same
// pruning carries it -- sort descending so big items place first, and skip
// any bucket whose sum equals an already-tried bucket's sum.
bool canPartitionKSubsets(vector<int> nums, int k) {
long long total = 0;
for (int num : nums) total += num;
if (total % k != 0) return false;
long long target = total / k;
sort(nums.rbegin(), nums.rend()); // descending: fail fast
if (nums[0] > target) return false;
int n = static_cast<int>(nums.size());
vector<long long> buckets(k, 0);
auto dfs = [&](auto&& self, int i) -> bool {
if (i == n) return true;
for (int b = 0; b < k; ++b) {
if (buckets[b] + nums[i] > target) continue;
bool symmetric = false; // equal-bucket skip
for (int prev = 0; prev < b; ++prev)
if (buckets[prev] == buckets[b]) {
symmetric = true;
break;
}
if (symmetric) continue;
buckets[b] += nums[i];
if (self(self, i + 1)) return true;
buckets[b] -= nums[i];
}
return false;
};
return dfs(dfs, 0);
}
/// LC 698. Matchsticks to Square with k buckets instead of 4: target is
/// total/k, sort descending, and apply the same equal-bucket skip so
/// interchangeable buckets are tried only once per element.
pub fn can_partition_k_subsets(nums: Vec<i32>, k: i32) -> bool {
fn dfs(nums: &[i32], idx: usize, buckets: &mut [i32], target: i32) -> bool {
if idx == nums.len() {
return true; // total == k * target, so every bucket is full
}
for b in 0..buckets.len() {
if buckets[b] + nums[idx] > target {
continue;
}
if buckets[..b].iter().any(|&s| s == buckets[b]) {
continue; // equal-bucket skip: same sum, same subtree
}
buckets[b] += nums[idx];
if dfs(nums, idx + 1, buckets, target) {
return true;
}
buckets[b] -= nums[idx];
}
false
}
let total: i32 = nums.iter().sum();
if total % k != 0 {
return false;
}
let target = total / k;
let mut sorted = nums;
sorted.sort_unstable_by(|a, b| b.cmp(a));
if sorted[0] > target {
return false;
}
dfs(&sorted, 0, &mut vec![0; k as usize], target)
}
/** LC 698. Matchsticks generalized to k buckets: sort descending, prune overflow, skip equal-sum buckets. */
export function canPartitionKSubsets(nums: number[], k: number): boolean {
const total = nums.reduce((a, b) => a + b, 0);
if (total % k !== 0) return false;
const target = total / k;
const sorted = [...nums].sort((a, b) => b - a);
if (sorted[0] > target) return false;
const buckets: number[] = new Array(k).fill(0);
function place(index: number): boolean {
if (index === sorted.length) return true;
for (let j = 0; j < k; j++) {
if (buckets[j] + sorted[index] > target) continue;
if (buckets.indexOf(buckets[j]) !== j) continue; // equal buckets are interchangeable
buckets[j] += sorted[index];
if (place(index + 1)) return true;
buckets[j] -= sorted[index];
}
return false;
}
return place(0);
}
// LC 698. Matchsticks to Square with k buckets targeting total/k; the same two
// prunings carry it: sort descending and skip equal-sum buckets.
func canPartitionKSubsets(nums []int, k int) bool {
total := 0
for _, num := range nums {
total += num
}
if total%k != 0 {
return false
}
target := total / k
sort.Sort(sort.Reverse(sort.IntSlice(nums))) // descending: fail fast
if nums[0] > target {
return false
}
buckets := make([]int, k)
var dfs func(i int) bool
dfs = func(i int) bool {
if i == len(nums) {
return true
}
for b := 0; b < k; b++ {
if buckets[b]+nums[i] > target {
continue
}
symmetric := false // equal-bucket skip
for prev := 0; prev < b; prev++ {
if buckets[prev] == buckets[b] {
symmetric = true
break
}
}
if symmetric {
continue
}
buckets[b] += nums[i]
if dfs(i + 1) {
return true
}
buckets[b] -= nums[i]
}
return false
}
return dfs(0)
}
// LC 698. Matchsticks to Square with k buckets: sort descending, and never
// drop a number into a bucket whose sum repeats one already tried for it.
func canPartitionKSubsets(_ nums: [Int], _ k: Int) -> Bool {
let total = nums.reduce(0, +)
if nums.isEmpty || total % k != 0 { return false }
let target = total / k
var nums = nums
nums.sort(by: >) // descending: doomed branches die near the root
if nums[0] > target { return false }
var buckets = [Int](repeating: 0, count: k)
func place(_ i: Int) -> Bool {
if i == nums.count { return true } // no bucket over target, sums to k * target
for b in 0..<k {
if buckets[b] + nums[i] > target { continue } // pruning 1: overflows
if (0..<b).contains(where: { buckets[$0] == buckets[b] }) { continue } // pruning 2: equal-sum bucket already failed
buckets[b] += nums[i]
if place(i + 1) { return true }
buckets[b] -= nums[i]
}
return false
}
return place(0)
}
15. N Queens
Hard · LC 51
Given n, return all boards placing n queens on an n by n grid so that no two attack each other, formatted with dots and Qs. Place one queen per row, looping over columns and recursing to the next row whenever the square is safe. Safety checks are O(1) with three hash sets, occupied columns plus the two diagonal directions keyed by r+c and r-c, each added before recursing and removed after.
def solve_n_queens(n: int) -> list[list[str]]:
"""LC 51. N-Queens.
Place one queen per row so rows can never clash, looping over
columns and recursing to the next row when the square is safe.
Safety is O(1) via three hash sets: occupied columns, the "/"
diagonals keyed by row + col, and the "\\" diagonals keyed by
row - col -- each key is constant along its line. Add before
recursing, remove after. O(n!) branching, O(n) sets plus output.
"""
boards: list[list[str]] = []
queen_cols: list[int] = [] # queen_cols[row] = column of that row's queen
taken_cols: set[int] = set()
taken_rising: set[int] = set() # row + col is constant on "/" diagonals
taken_falling: set[int] = set() # row - col is constant on "\" diagonals
def place(row: int) -> None:
if row == n:
boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queen_cols])
return
for col in range(n):
if col in taken_cols or row + col in taken_rising or row - col in taken_falling:
continue
queen_cols.append(col)
taken_cols.add(col)
taken_rising.add(row + col)
taken_falling.add(row - col)
place(row + 1)
queen_cols.pop() # undo all four marks before trying the next column
taken_cols.discard(col)
taken_rising.discard(row + col)
taken_falling.discard(row - col)
place(0)
return boards
// LC 51. Place one queen per row, looping over columns and recursing to the
// next row whenever the square is safe. Safety checks are O(1) with three
// hash sets -- occupied columns plus the two diagonal directions keyed by
// r-c and r+c -- each added before recursing and removed after.
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
unordered_set<int> cols, diag, antiDiag; // c, r-c, r+c
auto dfs = [&](auto&& self, int row) -> void {
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (cols.count(col) || diag.count(row - col) || antiDiag.count(row + col)) continue;
cols.insert(col);
diag.insert(row - col);
antiDiag.insert(row + col);
board[row][col] = 'Q';
self(self, row + 1);
board[row][col] = '.';
cols.erase(col);
diag.erase(row - col);
antiDiag.erase(row + col);
}
};
dfs(dfs, 0);
return ans;
}
/// LC 51. One queen per row, so only columns and diagonals need guarding:
/// three boolean Vecs indexed by col, r + c, and r - c + n - 1 make each
/// safety check O(1). Set all three before recursing, clear after; boards
/// are rendered only at the leaves from the queens' column list.
pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
struct State {
queens: Vec<usize>,
cols: Vec<bool>,
diag: Vec<bool>, // r + c, constant along "\" diagonals
anti: Vec<bool>, // r - c + n - 1, constant along "/" diagonals
}
fn dfs(row: usize, n: usize, st: &mut State, ans: &mut Vec<Vec<String>>) {
if row == n {
let board = st
.queens
.iter()
.map(|&c| {
let mut line = vec![b'.'; n];
line[c] = b'Q';
String::from_utf8(line).unwrap()
})
.collect();
ans.push(board);
return;
}
for col in 0..n {
let (d, a) = (row + col, row + n - 1 - col);
if st.cols[col] || st.diag[d] || st.anti[a] {
continue;
}
st.cols[col] = true;
st.diag[d] = true;
st.anti[a] = true;
st.queens.push(col);
dfs(row + 1, n, st, ans);
st.queens.pop();
st.cols[col] = false;
st.diag[d] = false;
st.anti[a] = false;
}
}
let n = n as usize;
let mut st = State {
queens: Vec::new(),
cols: vec![false; n],
diag: vec![false; 2 * n - 1],
anti: vec![false; 2 * n - 1],
};
let mut ans = Vec::new();
dfs(0, n, &mut st, &mut ans);
ans
}
/** LC 51. One queen per row; O(1) safety via sets for columns and diagonals keyed by r-c and r+c. */
export function solveNQueens(n: number): string[][] {
const ans: string[][] = [];
const cols = new Set<number>();
const diag = new Set<number>(); // r - c is constant along each "\" diagonal
const anti = new Set<number>(); // r + c is constant along each "/" diagonal
const queenCol: number[] = []; // queenCol[r] = column of the queen placed on row r
function placeRow(row: number): void {
if (row === n) {
ans.push(queenCol.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
cols.add(col);
diag.add(row - col);
anti.add(row + col);
queenCol.push(col);
placeRow(row + 1);
queenCol.pop();
cols.delete(col);
diag.delete(row - col);
anti.delete(row + col);
}
}
placeRow(0);
return ans;
}
// LC 51. One queen per row; sets for columns plus the r-c and r+c diagonals
// make safety O(1). Add the marks before recursing, remove them after.
func solveNQueens(n int) [][]string {
ans := [][]string{}
board := make([][]byte, n)
for r := range board {
board[r] = []byte(strings.Repeat(".", n))
}
cols := map[int]bool{}
diag := map[int]bool{} // r - c is constant on "\" diagonals
antiDiag := map[int]bool{} // r + c is constant on "/" diagonals
var dfs func(row int)
dfs = func(row int) {
if row == n {
snapshot := make([]string, n)
for r, line := range board {
snapshot[r] = string(line)
}
ans = append(ans, snapshot)
return
}
for col := 0; col < n; col++ {
if cols[col] || diag[row-col] || antiDiag[row+col] {
continue
}
cols[col] = true
diag[row-col] = true
antiDiag[row+col] = true
board[row][col] = 'Q'
dfs(row + 1)
board[row][col] = '.'
delete(cols, col)
delete(diag, row-col)
delete(antiDiag, row+col)
}
}
dfs(0)
return ans
}
// LC 51. One queen per row so rows never clash; O(1) safety via sets of taken
// columns and the r - c / r + c diagonals. Add before recursing, remove after.
func solveNQueens(_ n: Int) -> [[String]] {
var ans: [[String]] = []
var queenCols: [Int] = [] // queenCols[row] = column of that row's queen
var cols = Set<Int>()
var diag = Set<Int>() // row - col is constant on "\" diagonals
var antiDiag = Set<Int>() // row + col is constant on "/" diagonals
func place(_ row: Int) {
if row == n {
ans.append(queenCols.map { c in
String(repeating: ".", count: c) + "Q" + String(repeating: ".", count: n - c - 1)
})
return
}
for col in 0..<n {
if cols.contains(col) || diag.contains(row - col) || antiDiag.contains(row + col) { continue }
cols.insert(col)
diag.insert(row - col)
antiDiag.insert(row + col)
queenCols.append(col)
place(row + 1)
queenCols.removeLast() // undo all four marks before the next column
cols.remove(col)
diag.remove(row - col)
antiDiag.remove(row + col)
}
}
place(0)
return ans
}
16. N Queens II
Hard · LC 52
Given n, return only the number of distinct n-queens placements rather than the boards themselves. Run the same row-by-row backtracking as N Queens, with sets for columns and the two diagonals keyed by r+c and r-c, incrementing a counter on reaching row n. The point is identical machinery without board construction; bitmask versions pack the three sets into integers for extra speed.
def total_n_queens(n: int) -> int:
"""LC 52. N-Queens II.
Identical machinery to LC 51 -- one queen per row, sets for columns
and the two diagonals keyed by row + col and row - col -- but only a
counter increments on reaching row n; no boards are built. Bitmask
versions pack the three sets into integers for extra speed. O(n!)
branching, O(n) space.
"""
placements = 0
taken_cols: set[int] = set()
taken_rising: set[int] = set() # row + col
taken_falling: set[int] = set() # row - col
def place(row: int) -> None:
nonlocal placements
if row == n:
placements += 1
return
for col in range(n):
if col in taken_cols or row + col in taken_rising or row - col in taken_falling:
continue
taken_cols.add(col)
taken_rising.add(row + col)
taken_falling.add(row - col)
place(row + 1)
taken_cols.discard(col)
taken_rising.discard(row + col)
taken_falling.discard(row - col)
place(0)
return placements
// LC 52. Identical machinery to N Queens without board construction: sets for
// columns and the two diagonals keyed by r-c and r+c, incrementing a counter
// on reaching row n. (Bitmask versions pack the three sets into integers for
// extra speed.)
int totalNQueens(int n) {
int count = 0;
unordered_set<int> cols, diag, antiDiag; // c, r-c, r+c
auto dfs = [&](auto&& self, int row) -> void {
if (row == n) {
++count;
return;
}
for (int col = 0; col < n; ++col) {
if (cols.count(col) || diag.count(row - col) || antiDiag.count(row + col)) continue;
cols.insert(col);
diag.insert(row - col);
antiDiag.insert(row + col);
self(self, row + 1);
cols.erase(col);
diag.erase(row - col);
antiDiag.erase(row + col);
}
};
dfs(dfs, 0);
return count;
}
/// LC 52. Identical machinery to LC 51 without board construction: count a
/// completed row-n placement and move on.
pub fn total_n_queens(n: i32) -> i32 {
fn dfs(row: usize, n: usize, cols: &mut [bool], diag: &mut [bool], anti: &mut [bool]) -> i32 {
if row == n {
return 1;
}
let mut count = 0;
for col in 0..n {
let (d, a) = (row + col, row + n - 1 - col);
if cols[col] || diag[d] || anti[a] {
continue;
}
cols[col] = true;
diag[d] = true;
anti[a] = true;
count += dfs(row + 1, n, cols, diag, anti);
cols[col] = false;
diag[d] = false;
anti[a] = false;
}
count
}
let n = n as usize;
dfs(0, n, &mut vec![false; n], &mut vec![false; 2 * n - 1], &mut vec![false; 2 * n - 1])
}
/** LC 52. The LC 51 machinery counting completions instead of building boards. */
export function totalNQueens(n: number): number {
let count = 0;
const cols = new Set<number>();
const diag = new Set<number>();
const anti = new Set<number>();
function placeRow(row: number): void {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
cols.add(col);
diag.add(row - col);
anti.add(row + col);
placeRow(row + 1);
cols.delete(col);
diag.delete(row - col);
anti.delete(row + col);
}
}
placeRow(0);
return count;
}
// LC 52. Identical machinery to N Queens without board construction: just a
// counter that increments on reaching row n.
func totalNQueens(n int) int {
count := 0
cols := map[int]bool{}
diag := map[int]bool{} // r - c
antiDiag := map[int]bool{} // r + c
var dfs func(row int)
dfs = func(row int) {
if row == n {
count++
return
}
for col := 0; col < n; col++ {
if cols[col] || diag[row-col] || antiDiag[row+col] {
continue
}
cols[col] = true
diag[row-col] = true
antiDiag[row+col] = true
dfs(row + 1)
delete(cols, col)
delete(diag, row-col)
delete(antiDiag, row+col)
}
}
dfs(0)
return count
}
// LC 52. Identical machinery to N Queens -- cols plus the two diagonal sets --
// but only a counter increments at row n; no boards are built.
func totalNQueens(_ n: Int) -> Int {
var count = 0
var cols = Set<Int>()
var diag = Set<Int>() // row - col
var antiDiag = Set<Int>() // row + col
func place(_ row: Int) {
if row == n {
count += 1
return
}
for col in 0..<n {
if cols.contains(col) || diag.contains(row - col) || antiDiag.contains(row + col) { continue }
cols.insert(col)
diag.insert(row - col)
antiDiag.insert(row + col)
place(row + 1)
cols.remove(col)
diag.remove(row - col)
antiDiag.remove(row + col)
}
}
place(0)
return count
}
17. Word Break II
Hard · LC 140
Given a string s and a dictionary, return every sentence formed by inserting spaces so that each piece is a dictionary word. Backtrack over prefixes: for each dictionary word matching the front of the remaining suffix, recurse on the rest and prepend the word to every returned sentence. Memoizing the sentence list for each suffix start index avoids recomputing shared subproblems, turning overlapping branches into lookups.
def word_break_ii(s: str, word_dict: list[str]) -> list[str]:
"""LC 140. Word Break II.
Backtrack over prefixes: every dictionary word matching the front of
the current suffix recurses on the rest and prepends itself to each
sentence that comes back. Memoizing the sentence list per suffix
start index turns overlapping branches into lookups -- each suffix
is solved once no matter how many prefixes lead to it. Worst case
the output itself is O(2^n), so the bound is output-sized.
"""
words = set(word_dict)
longest = max(map(len, words), default=0) # no prefix can beat the longest word
suffix_sentences: dict[int, list[str]] = {}
def sentences(start: int) -> list[str]:
if start == len(s):
return [""] # one EMPTY sentence, not zero -- it seeds the joins below
if start in suffix_sentences:
return suffix_sentences[start]
built: list[str] = []
for end in range(start + 1, min(len(s), start + longest) + 1):
prefix = s[start:end]
if prefix not in words:
continue
for rest in sentences(end):
built.append(prefix if not rest else prefix + " " + rest)
suffix_sentences[start] = built
return built
return sentences(0)
// LC 140. Backtrack over prefixes: for each dictionary word matching the
// front of the remaining suffix, recurse on the rest and prepend the word to
// every returned sentence. Memoizing the sentence list for each suffix start
// index turns overlapping branches into lookups. (unordered_map references
// stay valid across inserts, so returning them is safe.)
vector<string> wordBreakII(string s, vector<string> wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = static_cast<int>(s.size());
unordered_map<int, vector<string>> memo; // start -> sentences for s[start..]
auto dfs = [&](auto&& self, int start) -> const vector<string>& {
auto found = memo.find(start);
if (found != memo.end()) return found->second;
vector<string> sentences;
for (int end = start + 1; end <= n; ++end) {
string word = s.substr(start, end - start);
if (!dict.count(word)) continue;
if (end == n) {
sentences.push_back(word);
} else {
for (const string& rest : self(self, end)) sentences.push_back(word + " " + rest);
}
}
return memo[start] = move(sentences);
};
return dfs(dfs, 0);
}
/// LC 140. Backtrack over prefixes: for each dictionary word matching the
/// front of the suffix at `start`, recurse on the rest and prepend the word
/// to every returned sentence. The memo maps each suffix start index to its
/// full sentence list, turning overlapping branches into clone-and-return.
pub fn word_break_ii(s: String, word_dict: Vec<String>) -> Vec<String> {
fn dfs(
s: &str,
start: usize,
words: &[String],
memo: &mut HashMap<usize, Vec<String>>,
) -> Vec<String> {
if let Some(cached) = memo.get(&start) {
return cached.clone();
}
let mut sentences = Vec::new();
if start == s.len() {
sentences.push(String::new()); // one empty sentence seeds the joins
} else {
for word in words {
if s[start..].starts_with(word.as_str()) {
for rest in dfs(s, start + word.len(), words, memo) {
if rest.is_empty() {
sentences.push(word.clone());
} else {
sentences.push(format!("{} {}", word, rest));
}
}
}
}
}
memo.insert(start, sentences.clone());
sentences
}
let mut memo = HashMap::new();
dfs(&s, 0, &word_dict, &mut memo)
}
/** LC 140. Backtrack over dictionary prefixes, memoizing the sentence list per suffix start index. */
export function wordBreakII(s: string, wordDict: string[]): string[] {
const words = new Set(wordDict);
const memo = new Map<number, string[]>(); // start index -> every sentence for s.slice(start)
function sentences(start: number): string[] {
const cached = memo.get(start);
if (cached) return cached;
const result: string[] = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (!words.has(word)) continue;
if (end === s.length) {
result.push(word); // the word finishes the string by itself
} else {
for (const rest of sentences(end)) result.push(word + " " + rest);
}
}
memo.set(start, result); // shared suffixes become lookups instead of re-exploration
return result;
}
return sentences(0);
}
// LC 140. Backtrack over prefixes, prepending each dictionary word to every
// sentence of the remaining suffix; memoize sentence lists per start index.
func wordBreakII(s string, wordDict []string) []string {
dict := map[string]bool{}
for _, w := range wordDict {
dict[w] = true
}
memo := map[int][]string{} // start -> sentences for s[start:]
var dfs func(start int) []string
dfs = func(start int) []string {
if cached, ok := memo[start]; ok {
return cached
}
sentences := []string{}
for end := start + 1; end <= len(s); end++ {
word := s[start:end]
if !dict[word] {
continue
}
if end == len(s) {
sentences = append(sentences, word)
} else {
for _, rest := range dfs(end) {
sentences = append(sentences, word+" "+rest)
}
}
}
memo[start] = sentences
return sentences
}
return dfs(0)
}
// LC 140. Backtrack over dictionary prefixes of the current suffix, prepending
// each to the sentences of the rest; memoize per suffix start so each suffix
// is solved once no matter how many prefixes lead to it.
func wordBreakII(_ s: String, _ wordDict: [String]) -> [String] {
let dict = Set(wordDict)
let chars = Array(s)
let n = chars.count
var memo: [Int: [String]] = [:] // start -> sentences for s[start...]
func sentences(_ start: Int) -> [String] {
if let cached = memo[start] { return cached }
var built: [String] = []
for end in (start + 1)..<(n + 1) {
let word = String(chars[start..<end])
if !dict.contains(word) { continue }
if end == n {
built.append(word)
} else {
for rest in sentences(end) { built.append(word + " " + rest) }
}
}
memo[start] = built
return built
}
return sentences(0)
}