Recursion & DP Problems

N-Queens Problem (20 points)

Find all valid placements of N queens on an N×N chessboard:

/**
 * N-Queens: Place N queens on N×N board so no two attack each other
 * Time: O(N!) with pruning
 */
public class NQueens {
    
    /**
     * Find all solutions for N-Queens
     * @return List of solutions, each solution is a list of column positions
     *         where result.get(i) = column of queen in row i
     */
    public List> solveNQueens(int n) {
        // Backtracking with row-by-row placement
    }
    
    /**
     * Find ONE valid solution (if exists)
     */
    public List solveNQueensOne(int n) {
        // Return first valid solution found
    }
    
    /**
     * Count total number of solutions
     */
    public int countNQueensSolutions(int n) {
        // Return count without storing all solutions
    }
    
    // Helper: check if placement is safe
    private boolean isSafe(int[] queens, int row, int col) {
        // Check column and diagonals
    }
    
    // Print board visualization
    public void printBoard(List solution) {
        // Display Q and . grid
    }
}

Requirements:

• Solve for N = 4, 8, and 12
• Print at least one solution as a visual board
• Report total solution count for each N

Permutations & Combinations (15 points)

Generate all permutations and combinations:

public class PermutationsCombinations {
    
    /**
     * Generate all permutations of array elements
     * [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     */
    public List> permute(int[] nums) {
        // Swap-based or used[] array approach
    }
    
    /**
     * Generate all permutations with duplicates
     * [1,1,2] → [[1,1,2],[1,2,1],[2,1,1]]
     */
    public List> permuteUnique(int[] nums) {
        // Handle duplicates - sort and skip same elements
    }
    
    /**
     * Generate all combinations of size k
     * [1,2,3,4], k=2 → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
     */
    public List> combine(int n, int k) {
        // Choose k from n
    }
    
    /**
     * Generate all subsets (power set)
     * [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
     */
    public List> subsets(int[] nums) {
        // Include/exclude each element
    }
}

Sudoku Solver (15 points)

Solve a 9×9 Sudoku puzzle using backtracking:

/**
 * Solve Sudoku puzzle using backtracking
 * Empty cells represented as 0
 */
public class SudokuSolver {
    
    /**
     * Solve the Sudoku puzzle in-place
     * @return true if solvable, false otherwise
     */
    public boolean solveSudoku(int[][] board) {
        // Find empty cell, try 1-9, backtrack if invalid
    }
    
    // Check if placing num at (row, col) is valid
    private boolean isValid(int[][] board, int row, int col, int num) {
        // Check row, column, and 3x3 box
    }
    
    // Print the board
    public void printBoard(int[][] board) {
        // Display formatted 9x9 grid
    }
}

Word Search in Grid (10 points)

Find if a word exists in a 2D character grid:

/**
 * Search for word in 2D grid (adjacent cells only)
 */
public boolean wordSearch(char[][] board, String word) {
    // Start DFS from each cell matching first character
    // Mark visited cells, backtrack when done
}

/**
 * Find all words from dictionary in grid (Word Search II)
 * Use Trie for efficient prefix matching
 */
public List findWords(char[][] board, String[] words) {
    // Build Trie, DFS with Trie prefix pruning
}

Generate Parentheses (10 points)

Generate all valid combinations of n pairs of parentheses:

/**
 * Generate all valid parentheses combinations
 * n=3 → ["((()))","(()())","(())()","()(())","()()()"]
 */
public List generateParenthesis(int n) {
    // Track open and close counts
    // Can add '(' if open < n
    // Can add ')' if close < open
}

Combination Sum Problems (10 points)

Find combinations that sum to a target:

/**
 * Combination Sum I: Can reuse same number
 * [2,3,6,7], target=7 → [[2,2,3],[7]]
 */
public List> combinationSum(int[] candidates, int target) {
    // Allow reusing elements
}

/**
 * Combination Sum II: Each number used once, with duplicates in input
 * [10,1,2,7,6,1,5], target=8 → [[1,1,6],[1,2,5],[1,7],[2,6]]
 */
public List> combinationSum2(int[] candidates, int target) {
    // Sort and skip duplicates
}

/**
 * Combination Sum III: Use k numbers from 1-9, each once
 * k=3, n=9 → [[1,2,6],[1,3,5],[2,3,4]]
 */
public List> combinationSum3(int k, int n) {
    // Choose exactly k numbers summing to n
}

Fibonacci & Climbing Stairs (15 points)

Warm-up DP problems:

/**
 * Fibonacci with memoization
 * Time: O(n), Space: O(n)
 */
public long fibMemo(int n, long[] memo) {
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
}

/**
 * Fibonacci with tabulation
 * Time: O(n), Space: O(n) or O(1) optimized
 */
public long fibTab(int n) {
    long[] dp = new long[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

/**
 * Climbing Stairs: n steps, can climb 1 or 2 at a time
 * How many distinct ways to reach the top?
 */
public int climbStairs(int n);

/**
 * Climbing Stairs with k steps: can climb 1 to k steps
 */
public int climbStairsK(int n, int k);

Longest Common Subsequence (25 points)

Classic 2D DP problem:

/**
 * LCS - Longest Common Subsequence
 * "ABCDGH", "AEDFHR" → "ADH" (length 3)
 */
public class LCS {
    
    /**
     * Memoization approach
     * Time: O(m*n), Space: O(m*n)
     */
    public int lcsMemo(String s1, String s2) {
        int[][] memo = new int[s1.length()][s2.length()];
        // Initialize with -1
        return lcsMemoHelper(s1, s2, s1.length()-1, s2.length()-1, memo);
    }
    
    /**
     * Tabulation approach
     * dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
     */
    public int lcsTab(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
    
    /**
     * Reconstruct the actual LCS string
     */
    public String getLCS(String s1, String s2) {
        // Backtrack through DP table
    }
    
    /**
     * Space-optimized: O(min(m,n)) space
     */
    public int lcsOptimized(String s1, String s2) {
        // Use only two rows
    }
}

Longest Increasing Subsequence (20 points)

Find longest strictly increasing subsequence:

/**
 * LIS - Longest Increasing Subsequence
 * [10,9,2,5,3,7,101,18] → [2,3,7,101] (length 4)
 */
public class LIS {
    
    /**
     * O(n²) DP solution
     * dp[i] = length of LIS ending at index i
     */
    public int lisDP(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().orElse(0);
    }
    
    /**
     * O(n log n) solution using binary search
     */
    public int lisBinarySearch(int[] nums) {
        // Maintain sorted array of smallest tail elements
    }
    
    /**
     * Reconstruct the actual LIS
     */
    public List getLIS(int[] nums) {
        // Track parent pointers
    }
}

Edit Distance (20 points)

Minimum operations to convert one string to another:

/**
 * Edit Distance (Levenshtein Distance)
 * Operations: insert, delete, replace
 * "horse" → "ros" = 3 (replace h→r, remove r, remove e)
 */
public class EditDistance {
    
    /**
     * Memoization approach
     */
    public int editDistMemo(String s1, String s2) {
        int[][] memo = new int[s1.length() + 1][s2.length() + 1];
        // Initialize with -1
        return helper(s1, s2, s1.length(), s2.length(), memo);
    }
    
    /**
     * Tabulation approach
     * dp[i][j] = min ops to convert s1[0..i-1] to s2[0..j-1]
     */
    public int editDistTab(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // Base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        
        // Fill table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i-1][j-1],  // replace
                        Math.min(dp[i-1][j], dp[i][j-1])  // delete or insert
                    );
                }
            }
        }
        return dp[m][n];
    }
    
    /**
     * Get the sequence of operations
     */
    public List getOperations(String s1, String s2) {
        // Backtrack through DP table
    }
}

0/1 Knapsack Problem (25 points)

Classic optimization problem:

/**
 * 0/1 Knapsack: Maximize value with weight constraint
 * Each item can be taken at most once
 */
public class Knapsack {
    
    /**
     * Memoization approach
     */
    public int knapsackMemo(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] memo = new int[n][capacity + 1];
        // Initialize with -1
        return helper(weights, values, n - 1, capacity, memo);
    }
    
    /**
     * Tabulation approach
     * dp[i][w] = max value using items 0..i with capacity w
     */
    public int knapsackTab(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                // Don't take item i
                dp[i][w] = dp[i-1][w];
                // Take item i if it fits
                if (weights[i-1] <= w) {
                    dp[i][w] = Math.max(dp[i][w], 
                        dp[i-1][w - weights[i-1]] + values[i-1]);
                }
            }
        }
        return dp[n][capacity];
    }
    
    /**
     * Space-optimized: O(capacity) space
     */
    public int knapsackOptimized(int[] weights, int[] values, int capacity) {
        // Use single 1D array, iterate backwards
    }
    
    /**
     * Return which items to take
     */
    public List getItems(int[] weights, int[] values, int capacity) {
        // Backtrack through DP table
    }
}

Coin Change Problems (25 points)

Different variations of the coin change problem:

/**
 * Coin Change I: Minimum coins to make amount
 * coins = [1,2,5], amount = 11 → 3 (5+5+1)
 */
public int coinChangeMin(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

/**
 * Coin Change II: Number of ways to make amount
 * coins = [1,2,5], amount = 5 → 4 ways
 * (5), (2+2+1), (2+1+1+1), (1+1+1+1+1)
 */
public int coinChangeWays(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

/**
 * Return the coins used for minimum solution
 */
public List getCoinsUsed(int[] coins, int amount) {
    // Track which coin was used at each amount
}

Matrix Chain Multiplication (20 points)

Minimize scalar multiplications for matrix chain:

/**
 * Matrix Chain Multiplication
 * Find optimal parenthesization to minimize multiplications
 * dimensions = [10, 20, 30, 40, 30]
 * Matrices: A1(10x20), A2(20x30), A3(30x40), A4(40x30)
 */
public class MatrixChain {
    
    /**
     * Memoization approach
     */
    public int mcmMemo(int[] dims) {
        int n = dims.length - 1;  // number of matrices
        int[][] memo = new int[n][n];
        // Initialize with -1
        return helper(dims, 0, n - 1, memo);
    }
    
    /**
     * Tabulation approach
     * dp[i][j] = min cost to multiply matrices i to j
     */
    public int mcmTab(int[] dims) {
        int n = dims.length - 1;
        int[][] dp = new int[n][n];
        
        // len is chain length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k+1][j] 
                        + dims[i] * dims[k+1] * dims[j+1];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n-1];
    }
    
    /**
     * Print optimal parenthesization
     */
    public String getParenthesization(int[] dims) {
        // Track split points and reconstruct
    }
}

Longest Palindromic Subsequence (20 points)

Find longest palindromic subsequence in a string:

/**
 * Longest Palindromic Subsequence
 * "bbbab" → "bbbb" (length 4)
 */
public class LPS {
    
    /**
     * Memoization approach
     */
    public int lpsMemo(String s) {
        int n = s.length();
        int[][] memo = new int[n][n];
        return helper(s, 0, n - 1, memo);
    }
    
    /**
     * Tabulation approach
     * dp[i][j] = LPS length for s[i..j]
     */
    public int lpsTab(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        // Base case: single characters
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        
        // Fill for increasing lengths
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
    
    /**
     * Get the actual palindrome
     */
    public String getLPS(String s) {
        // Backtrack through DP table
    }
    
    /**
     * Alternative: LPS = LCS(s, reverse(s))
     */
    public int lpsUsingLCS(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        return lcs(s, rev);
    }
}