Overview of Backtracking

Backtracking is a systematic way to explore all potential solutions by building combinations incrementally and backtracking when a path fails to meet constraints. It's particularly useful for problems like combinations, permutations, subsets, and other combinatorial searches.

Common problem types solved with backtracking include:

• Combination problems: Selecting k elements from a set of n without considering order.
• Sum-based combination problems: Finding combinations that sum up to a target.
• Letter combination problems: Generating all possible letter combinations for a phone number input.

Combinations differ from permutations in that the order of elements does not matter in combinations.

LeetCode 77: Combinations

The task is to generate all possible combinations of k numbers chosen from 1 to n.

Approach:

• Use a recursive backtracking function.
• Maintain a temporary list to store the current combination.
• When the combination reaches size k, add it to the result list.
• Recursively choose the next number, ensuring no duplicates.

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        generate(result, current, n, k, 1);
        return result;
    }

    private void generate(List<List<Integer>> result, List<Integer> current, int n, int k, int start) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i <= n; i++) {
            current.add(i);
            generate(result, current, n, k, i + 1);
            current.remove(current.size() - 1);
        }
    }
}

LeetCode 216: Combination Sum III

Find all unique combinations of k numbers that sum up to a target value n, using numbers from 1 to 9.

Approach:

• Similar to the previous problem but with an additional sum constraint.
• Track the remaining target sum during recursion.
• Prune the search space when the sum exceeds the target or the combination size exceeds k.

class Solution216 {
    public List<List<Integer>> combinationSum3(int k, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        generate(result, current, k, target, 1);
        return result;
    }

    private void generate(List<List<Integer>> result, List<Integer> current, int k, int remaining, int start) {
        if (current.size() == k && remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        if (current.size() >= k || remaining < 0) {
            return;
        }

        for (int i = start; i <= 9; i++) {
            current.add(i);
            generate(result, current, k, remaining - i, i + 1);
            current.remove(current.size() - 1);
        }
    }
}

LeetCode 17: Letter Combinations of a Phone Number

Generate all possible letter combinations that a given phone number could represent, based on standard telephone keypad mappings.

Approach:

• Create a mapping from digits to letters using a hash map.
• Use backtracking to explore all combinations of letters.
• Each recursive call processes the next digit and tries all its corresponding letters.

class Solution17 {
    private static final Map<Character, String> digitToLetters = new HashMap<>();

    static {
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;

        backtrack(result, new StringBuilder(), digits, 0);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder current, String digits, int position) {
        if (position == digits.length()) {
            result.add(current.toString());
            return;
        }

        char digit = digits.charAt(position);
        String letters = digitToLetters.get(digit);

        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(result, current, digits, position + 1);
            current.deleteCharAt(current.length() - 1);
        }
    }
}