Fading Coder

One Final Commit for the Last Sprint

Home > Notes > Content

Backtracking Algorithms in Depth

Notes Apr 20 17

Core Concepts

Backtracking is a systematic search method that explores all potential configurations of a solution space. It can be visualized as traversing a tree structure where the width represents the size of the candidate set and the depth corresponds to the recursion level.

Genarel Framework

A typical backtracking algorithm involves:

  1. A recursive function that builds candidate solutions incrementally.
  2. A termination condition to record a valid solution.
  3. A mechanism to undo the last choice (backtrack) and explore alternative paths.

Combination Problems

Generating k-combinations from 1..n

Find all possible k-length combinations from numbers 1 to n.

import java.util.*;

class CombinationsFinder {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> generateCombinations(int n, int k) {
        exploreCombinations(1, n, k);
        return result;
    }

    private void exploreCombinations(int startNum, int maxNum, int comboSize) {
        if (currentPath.size() == comboSize) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        int remainingSlots = comboSize - currentPath.size();
        for (int num = startNum; num <= maxNum && (maxNum - num + 1) >= remainingSlots; num++) {
            currentPath.add(num);
            exploreCombinations(num + 1, maxNum, comboSize);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Letter Combinations from Phone Digits

Given a string of digits (2-9), return all possible letter combinations.

import java.util.*;

class PhoneLetterCombiner {
    private List<String> output = new ArrayList<>();
    private StringBuilder currentString = new StringBuilder();
    private static final String[] digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> getCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return output;
        buildCombinations(0, digits);
        return output;
    }

    private void buildCombinations(int index, String digits) {
        if (index == digits.length()) {
            output.add(currentString.toString());
            return;
        }
        String letters = digitMap[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            currentString.append(letter);
            buildCombinations(index + 1, digits);
            currentString.deleteCharAt(currentString.length() - 1);
        }
    }
}

Finding Combination Sum

Find all unique combinations where numbers sum to a target. Elements can be reused.

import java.util.*;

class SumCombinationsFinder {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> findCombinationsForTarget(int[] candidates, int target) {
        searchCombinations(0, candidates, target);
        return result;
    }

    private void searchCombinations(int startIdx, int[] candidates, int remainingTarget) {
        if (remainingTarget == 0) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        if (remainingTarget < 0) return;
        
        for (int i = startIdx; i < candidates.length; i++) {
            currentPath.add(candidates[i]);
            searchCombinations(i, candidates, remainingTarget - candidates[i]);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Combination Sum with Duplicates

Find unique combinations summing to a target from a list with duplicates, using each number once.

import java.util.*;

class UniqueSumCombinationsFinder {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> findUniqueCombinations(int[] candidates, int target) {
        Arrays.sort(candidates);
        searchCombinations(0, candidates, target);
        return result;
    }

    private void searchCombinations(int startIdx, int[] candidates, int remainingTarget) {
        if (remainingTarget == 0) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        if (remainingTarget < 0) return;
        
        for (int i = startIdx; i < candidates.length; i++) {
            if (i > startIdx && candidates[i] == candidates[i-1]) continue;
            currentPath.add(candidates[i]);
            searchCombinations(i + 1, candidates, remainingTarget - candidates[i]);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Combination Sum III

Find all k-digit combinations from 1-9 summing to n.

import java.util.*;

class DigitSumCombinations {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> findCombinations(int k, int n) {
        findDigitCombinations(1, k, n);
        return result;
    }

    private void findDigitCombinations(int startDigit, int digitsLeft, int remainingSum) {
        if (remainingSum == 0 && digitsLeft == 0) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        if (remainingSum < 0 || digitsLeft == 0) return;
        
        for (int digit = startDigit; digit <= 9; digit++) {
            currentPath.add(digit);
            findDigitCombinations(digit + 1, digitsLeft - 1, remainingSum - digit);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Partition Problems

Palindrome Partitioning

Partition a string into all possible palindrome substrings.

import java.util.*;

class PalindromePartitioner {
    private List<List<String>> result = new ArrayList<>();
    private List<String> currentPath = new ArrayList<>();

    public List<List<String>> partitionString(String s) {
        partition(0, s);
        return result;
    }

    private void partition(int startIdx, String s) {
        if (startIdx == s.length()) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        for (int endIdx = startIdx; endIdx < s.length(); endIdx++) {
            if (isPalindrome(s, startIdx, endIdx)) {
                currentPath.add(s.substring(startIdx, endIdx + 1));
                partition(endIdx + 1, s);
                currentPath.remove(currentPath.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

Restoring IP Addresses

Generate all valid IP address combinations from a string of digits.

import java.util.*;

class IPAddressRestorer {
    private List<String> result = new ArrayList<>();
    private List<String> segments = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        buildAddresses(0, s);
        return result;
    }

    private void buildAddresses(int startIdx, String s) {
        if (segments.size() == 4 && startIdx == s.length()) {
            result.add(String.join(".", segments));
            return;
        }
        if (segments.size() >= 4 || startIdx >= s.length()) return;
        
        for (int len = 1; len <= 3 && startIdx + len <= s.length(); len++) {
            String segment = s.substring(startIdx, startIdx + len);
            if (isValidSegment(segment)) {
                segments.add(segment);
                buildAddresses(startIdx + len, s);
                segments.remove(segments.size() - 1);
            }
        }
    }

    private boolean isValidSegment(String segment) {
        if (segment.length() > 1 && segment.startsWith("0")) return false;
        int val = Integer.parseInt(segment);
        return val >= 0 && val <= 255;
    }
}

Subset Generation

All Subsets

Generate all subsets of a distinct integer array.

import java.util.*;

class SubsetGenerator {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> generateSubsets(int[] nums) {
        generate(0, nums);
        return result;
    }

    private void generate(int startIdx, int[] nums) {
        result.add(new ArrayList<>(currentPath));
        for (int i = startIdx; i < nums.length; i++) {
            currentPath.add(nums[i]);
            generate(i + 1, nums);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Subsets with Duplicates

Generate all unique subsets from an integer array that may contain duplicates.

import java.util.*;

class UniqueSubsetGenerator {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> generateUniqueSubsets(int[] nums) {
        Arrays.sort(nums);
        generate(0, nums);
        return result;
    }

    private void generate(int startIdx, int[] nums) {
        result.add(new ArrayList<>(currentPath));
        for (int i = startIdx; i < nums.length; i++) {
            if (i > startIdx && nums[i] == nums[i-1]) continue;
            currentPath.add(nums[i]);
            generate(i + 1, nums);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Permutation Problems

All Permutations

Generate all permutations of a distinct integer array.

import java.util.*;

class PermutationGenerator {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();
    private boolean[] used;

    public List<List<Integer>> generatePermutations(int[] nums) {
        used = new boolean[nums.length];
        generate(nums);
        return result;
    }

    private void generate(int[] nums) {
        if (currentPath.size() == nums.length) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            currentPath.add(nums[i]);
            generate(nums);
            currentPath.remove(currentPath.size() - 1);
            used[i] = false;
        }
    }
}

Unique Permutations

Generate all unique permutations from an integer array with duplicates.

import java.util.*;

class UniquePermutationGenerator {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();
    private boolean[] used;

    public List<List<Integer>> generateUniquePermutations(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        generate(nums);
        return result;
    }

    private void generate(int[] nums) {
        if (currentPath.size() == nums.length) {
            result.add(new ArrayList<>(currentPath));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
            used[i] = true;
            currentPath.add(nums[i]);
            generate(nums);
            currentPath.remove(currentPath.size() - 1);
            used[i] = false;
        }
    }
}

Grid-based Challenges

N-Queens Puzzle

Place N queens on an N×N chessboard so no two queens attack each other.

import java.util.*;

class NQueensSolver {
    private List<List<String>> solutions = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        placeQueen(0, n, board);
        return solutions;
    }

    private void placeQueen(int row, int n, char[][] board) {
        if (row == n) {
            solutions.add(constructSolution(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, board)) {
                board[row][col] = 'Q';
                placeQueen(row + 1, n, board);
                board[row][col] = '.';
            }
        }
    }

    private boolean isSafe(int row, int col, char[][] board) {
        for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false;
        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 List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) solution.add(new String(row));
        return solution;
    }
}

Sudoku Solver

Solve a 9x9 Sudoku puzzle.

class SudokuSolver {
    public void solve(char[][] board) {
        solveSudoku(0, 0, board);
    }

    private boolean solveSudoku(int row, int col, char[][] board) {
        if (row == 9) return true;
        if (col == 9) return solveSudoku(row + 1, 0, board);
        if (board[row][col] != '.') return solveSudoku(row, col + 1, board);
        
        for (char num = '1'; num <= '9'; num++) {
            if (isValidPlacement(row, col, num, board)) {
                board[row][col] = num;
                if (solveSudoku(row, col + 1, board)) return true;
                board[row][col] = '.';
            }
        }
        return false;
    }

    private boolean isValidPlacement(int row, int col, char num, char[][] board) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num) return false;
        }
        int boxRowStart = 3 * (row / 3), boxColStart = 3 * (col / 3);
        for (int r = boxRowStart; r < boxRowStart + 3; r++) {
            for (int c = boxColStart; c < boxColStart + 3; c++) {
                if (board[r][c] == num) return false;
            }
        }
        return true;
    }
}

Miscellaneous Challenges

Finding Increasing Subsequences

Find all increasing subsequences of at least length 2 from an integer array.

import java.util.*;

class IncreasingSubsequenceFinder {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        find(0, nums);
        return result;
    }

    private void find(int startIdx, int[] nums) {
        if (currentPath.size() >= 2) result.add(new ArrayList<>(currentPath));
        Set<Integer> seenInLevel = new HashSet<>();
        for (int i = startIdx; i < nums.length; i++) {
            if ((!currentPath.isEmpty() && nums[i] < currentPath.get(currentPath.size()-1)) || seenInLevel.contains(nums[i])) continue;
            seenInLevel.add(nums[i]);
            currentPath.add(nums[i]);
            find(i + 1, nums);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

Reconstructing Flight Itinerary

Reconstruct an itinerary from a list of airline tickets starting from JFK.

import java.util.*;

class ItineraryReconstructor {
    private List<String> route = new ArrayList<>();
    private Map<String, PriorityQueue<String>> flights = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            flights.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        }
        visitAirport("JFK");
        Collections.reverse(route);
        return route;
    }

    private void visitAirport(String airport) {
        PriorityQueue<String> destinations = flights.getOrDefault(airport, new PriorityQueue<>());
        while (!destinations.isEmpty()) {
            visitAirport(destinations.poll());
        }
        route.add(airport);
    }
}
Tags: Backtracking
Back to List

Prev: Statistical Analysis with t-Distributions and t-Tests in R

Next: Dynamic Memory Allocation and Generic Programming in C++

Related Articles

Designing Alertmanager Templates for Prometheus Notifications

How to craft Alertmanager templates to format alert messages, improving clarity and presentation. Alertmanager uses Go’s text/template engine with additional helper functions. Alerting rules referenc...

Deploying a Maven Web Application to Tomcat 9 Using the Tomcat Manager

Tomcat 9 does not provide a dedicated Maven plugin. The Tomcat Manager interface, however, is backward-compatible, so the Tomcat 7 Maven Plugin can be used to deploy to Tomcat 9. This guide shows two...

Spring Boot MyBatis with Two MySQL DataSources Using Druid

Required dependencies application.properties: define two data sources and poooling Java configuration for both data sources MyBatis mappers for each data source Controller endpoints to verify both co...

Leave a Comment

Anonymous

◎Feel free to join the discussion and share your thoughts.

Copyright © fadingcoder.top