Recursion and Backtracking Questions

def dfs_traverse(graph, start):
    visited = set()
    def dfs(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs(v)
    dfs(start)
    return visited

def permute(nums):
    res = []
    used = [False]*len(nums)
    path = []
    def backtrack():
        if len(path) == len(nums):
            res.append(path.copy()); return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()         # undo choice
            used[i] = False    # allow reuse in other branches
    backtrack()
    return res

public class StringReverser {
    public static String reverseString(String s) {
        if (s == null) return null;                 // handle null
        int n = s.length();
        if (n <= 1) return s;                       // base case: empty or single char
        return reverseString(s.substring(1)) + s.charAt(0); // recursive step
    }
}

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;

class StringReverserTest {
    @Test void testSingleChar() { assertEquals("a", StringReverser.reverseString("a")); }
    @Test void testEmpty()      { assertEquals("", StringReverser.reverseString("")); }
    @Test void testNull()       { assertNull(StringReverser.reverseString(null)); }
    @Test void testNormal()     { assertEquals("cba", StringReverser.reverseString("abc")); }
    @Test void testPalindrome() { assertEquals("racecar", StringReverser.reverseString("racecar")); }
}

public static String reverseStringFast(String s) {
    if (s == null) return null;
    char[] buf = s.toCharArray();
    reverseHelper(buf, 0, buf.length - 1);
    return new String(buf);
}
private static void reverseHelper(char[] b, int l, int r) {
    if (l >= r) return;
    char t = b[l]; b[l] = b[r]; b[r] = t;
    reverseHelper(b, l+1, r-1);
}

import java.util.*;

public class Hamiltonian {
    // n <= 15
    public static List<List<Integer>> hamiltonianPaths(int n, List<List<Integer>> adj) {
        List<List<Integer>> result = new ArrayList<>();
        int ALL_VISITED = (1 << n) - 1;
        int[] degree = new int[n];
        for (int i = 0; i < n; i++) degree[i] = adj.get(i).size();

        for (int start = 0; start < n; start++) {
            LinkedList<Integer> path = new LinkedList<>();
            path.add(start);
            dfs(start, 1 << start, path, result, adj, degree, ALL_VISITED);
        }
        return result;
    }

    private static void dfs(int u, int visited, LinkedList<Integer> path, List<List<Integer>> adj,
                            int[] degree, int ALL_VISITED) {
        if (visited == ALL_VISITED) {
            resultAdd(path, adj); // will be defined below via static capture
            return;
        }

        // Connectivity prune: quick check that all unvisited nodes are reachable from u in induced subgraph
        if (!remainingConnected(u, visited, adj, Integer.bitCount(ALL_VISITED ^ visited))) return;

        // Order neighbors by heuristic: fewest free-neighbors first (better branching)
        List<Integer> cand = new ArrayList<>();
        for (int v : adj.get(u)) if ((visited & (1 << v)) == 0) cand.add(v);
        cand.sort(Comparator.comparingInt(a -> freeNeighborCount(a, visited, adj)));

        for (int v : cand) {
            path.add(v);
            dfs(v, visited | (1 << v), path, adj, degree, ALL_VISITED);
            path.removeLast();
        }
    }

    // count unvisited neighbors of x
    private static int freeNeighborCount(int x, int visited, List<List<Integer>> adj) {
        int cnt = 0;
        for (int w : adj.get(x)) if ((visited & (1 << w)) == 0) cnt++;
        return cnt;
    }

    // check connectivity of remaining nodes (including current u) using BFS on induced subgraph
    private static boolean remainingConnected(int u, int visited, List<List<Integer>> adj, int remCount) {
        int maskRem = (~visited);
        int start = u;
        boolean[] seen = new boolean[adj.size()];
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(start);
        seen[start] = true;
        int seenCount = ((visited & (1 << start)) == 0) ? 1 : 0; // if start was unvisited (rare)
        while (!dq.isEmpty()) {
            int x = dq.poll();
            for (int y : adj.get(x)) {
                if ((maskRem & (1 << y)) != 0 && !seen[y]) {
                    seen[y] = true;
                    seenCount++;
                    dq.add(y);
                }
            }
        }
        // Note: we must ensure all remCount nodes are reachable; seenCount counts only unvisited reached
        return seenCount == remCount;
    }

    // helper to add snapshot to result (to avoid exposing static fields)
    private static final List<List<Integer>> resultCollector = new ArrayList<>();
    private static void resultAdd(LinkedList<Integer> path, List<List<Integer>> adj) {
        resultCollector.add(new ArrayList<>(path));
    }
}

def backtrack(path, choices, results):
    # path is mutated but we undo changes (backtrack) after recursion
    if is_solution(path):
        results.append(list(path))  # append a copy to avoid aliasing
        return
    for c in choices_for(path):
        if should_prune(path, c):  # implement pruning based on constraints
            continue
        path.append(c)
        backtrack(path, choices, results)
        path.pop()  # undo change so siblings start with correct state

from typing import Iterator, List

def combinations_lazy(n: int, k: int) -> Iterator[List[int]]:
    # yield combinations as lists of indices [0..n-1]
    buf = [0]*k
    def backtrack(start: int, depth: int):
        if depth == k:
            yield buf.copy()
            return
        # prune: need at least (k-depth) elements remaining
        for i in range(start, n - (k - depth) + 1):
            buf[depth] = i
            yield from backtrack(i+1, depth+1)
    yield from backtrack(0, 0)