Backtracking

Letter Combinations of a Phone Number

Link: https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Code:

class Solution {
    List<String> combinations = new ArrayList();
    Map<Character, String> letterMap = new HashMap<>();
    String phoneDigits;
    public List<String> letterCombinations(String digits) {
        letterMap.put('2', "abc");
        letterMap.put('3', "def");
        letterMap.put('4', "ghi");
        letterMap.put('5', "jkl");
        letterMap.put('6', "mno");
        letterMap.put('7', "pqrs");
        letterMap.put('8', "tuv");
        letterMap.put('9', "wxyz");
        // If the input is empty, immediately return an empty answer array
        if (digits.isEmpty()) {
            return combinations;
        }
        
        // Initiate backtracking with an empty path and starting index of 0
        phoneDigits = digits;
        backtrack(0, new StringBuilder());
        return combinations;
    }
    
    void backtrack(int index, StringBuilder path) {
        // if the path is the same length as digits, we have a complete combination
        if (path.length() == phoneDigits.length()) {
            combinations.add(path.toString());
            return; // backtrack
        }
        
        // get the letters that the current digit maps to, and loop through them
        String possibleLetters = letterMap.get(phoneDigits.charAt(index));
        for (char letter: possibleLetters.toCharArray()) {
            // add the letter to our current path
            path.append(letter);
            // move to the next digit
            backtrack(index + 1, path);
            // backtrack by removing the letter before moving onto the next
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Combination Sum

link: https://leetcode.com/problems/combination-sum/

Code:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        LinkedList<Integer> comb = new LinkedList<Integer>();
        backtrack(target, comb, 0, candidates, results);
        return results;
    }
    
    void backtrack(
            int remain,
            LinkedList<Integer> comb,
            int start,
            int[] candidates,
            List<List<Integer>> results) {
        if (remain == 0) {
            // make a deep copy of the current combination
            results.add(new ArrayList<Integer>(comb));
            return;
        } else if (remain < 0) {
            // exceed the scope, stop exploration.
            return;
        }
        
        for (int i = start; i < candidates.length; ++i) {
            // add the number to the combination
            comb.add(candidates[i]);
            backtrack(remain - candidates[i], comb, i, candidates, results);
            // backtrack, remove the number from the combination
            comb.removeLast();
        }
    }
}