Advanced Java Day 4: Advanced Recursion & Backtracking

Goal of this Day

Today you will learn:

• Recursive algorithms for permutations and combinations
• Backtracking basics (examples: Sudoku, maze solving)
• Optimizing recursion with memoization and introduction to dynamic programming

By the end, you will be able to write advanced recursive solutions and use backtracking techniques efficiently.

Step 1: Simple Recursion

A basic recursive method prints numbers from 1 to n:

public static void printNumbers(int n) {
    if(n == 0) return;
    printNumbers(n - 1);
    System.out.println(n);
}

Step 2: Recursive Algorithms – Permutations & Combinations

Recursion is commonly used to generate permutations or combinations of a set of elements.

// Example: Permutations of a string
public static void permute(String str, String prefix) {
    if(str.length() == 0) {
        System.out.println(prefix);
    } else {
        for(int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permute(rem, prefix + str.charAt(i));
        }
    }
}

Step 3: Backtracking Basics

Backtracking is a technique to explore all possible solutions and undo choices when necessary.

Examples:

• Sudoku solver
• Maze solving
• N-Queens problem

Step 4: Optimizing Recursion

Memoization stores results of subproblems to avoid repeated computation.

Map<Integer, Integer> memo = new HashMap<>();

public static int fibonacci(int n) {
    if(n <= 1) return n;
    if(memo.containsKey(n)) return memo.get(n);

    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result);
    return result;
}

Practice

public static void printNumbers(int n){
    if(n == 0) return;
    printNumbers(n - 1);
    System.out.println(n);
}

Exercise

Write a recursive program to generate all subsets of a set.

Steps:

• Define a recursive function that tracks the current index and current subset
• At each step, include or exclude the current element
• Print the subset when the index reaches the end of the set

Example:

import java.util.*;

public class Subsets {
    public static void generateSubsets(int[] arr, List<Integer> subset, int index) {
        if(index == arr.length) {
            System.out.println(subset);
            return;
        }

        // Include current element
        subset.add(arr[index]);
        generateSubsets(arr, subset, index + 1);

        // Exclude current element
        subset.remove(subset.size() - 1);
        generateSubsets(arr, subset, index + 1);
    }

    public static void main(String[] args) {
        int[] set = {1, 2, 3};
        generateSubsets(set, new ArrayList<>(), 0);
    }
}