Backtracking Pattern

import java.util.*;
public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private static void backtrack(int[] nums, int start,
                                 List<Integer> current,
                                 List<List<Integer>> result) {
        // Add current subset to result
        result.add(new ArrayList<>(current));
        // Try adding each remaining number
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);              // Choose
            backtrack(nums, i + 1, current, result);  // Explore
            current.remove(current.size() - 1); // Backtrack (undo)
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = subsets(nums);
        System.out.println("All subsets:");
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
        // Output: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
    }
}

import java.util.*;
public class NQueens {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        // Initialize board with empty spaces
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(board, 0, result);
        return result;
    }
    private static void backtrack(char[][] board, int row,
                                 List<List<String>> result) {
        // Base case: placed all queens
        if (row == board.length) {
            result.add(construct(board));
            return;
        }
        // Try placing queen in each column of current row
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';        // Choose
                backtrack(board, row + 1, result);  // Explore
                board[row][col] = '.';         // Backtrack
            }
        }
    }
    private static boolean isValid(char[][] board, int row, int col) {
        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // Check diagonal (top-left)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // Check diagonal (top-right)
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    private static List<String> construct(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }
    public static void main(String[] args) {
        int n = 4;
        List<List<String>> solutions = solveNQueens(n);
        System.out.println("Solutions for " + n + "-Queens:");
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

import java.util.*;
public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack("", 0, 0, n, result);
        return result;
    }
    private static void backtrack(String current, int open, int close,
                                 int max, List<String> result) {
        // Base case: used all parentheses
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        // Add opening parenthesis if we can
        if (open < max) {
            backtrack(current + "(", open + 1, close, max, result);
        }
        // Add closing parenthesis if valid
        if (close < open) {
            backtrack(current + ")", open, close + 1, max, result);
        }
    }
    public static void main(String[] args) {
        int n = 3;
        List<String> result = generateParenthesis(n);
        System.out.println("Valid parentheses for n=" + n + ":");
        for (String s : result) {
            System.out.println(s);
        }
        // Output: ((())), (()()), (())(), ()(()), ()()()
    }
}