代码随想录 Day25 - 回溯（二）

package jjn.carl.backtrack;
import java.util.ArrayList;
import java.util.List;
/**
 * @author Jiang Jining
 * @since 2023-07-23 22:19
 */
public class LeetCode216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(k, n, new ArrayList<>(), result, 0, 1);
        return result;
    }
    private void backtrack(int k, int n, List<Integer> path, List<List<Integer>> result, int sum, int startIndex) {
        if (path.size() > k || sum > n) {
            return;
        }
        if (path.size() == k && sum == n) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < 10; i++) {
            path.add(i);
            sum += i;
            backtrack(k, n, path, result, sum, i + 1);
            path.remove(path.size() - 1);
            sum -= i;
        }
    }
    public static void main(String[] args) {
        System.out.println("new LeetCode216().combinationSum3(3, 7) = " + new LeetCode216().combinationSum3(3, 7));
        System.out.println("new LeetCode216().combinationSum3(3, 9) = " + new LeetCode216().combinationSum3(3, 9));
    }
}

package jjn.carl.backtrack;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
 * @author Jiang Jining
 * @since 2023-07-23 22:43
 */
public class LeetCode17 {
    private static final Map<Character, List<String>> KEY_MAP = Map.of('2', List.of("a", "b", "c"),
            '3', List.of("d", "e", "f"), '4', List.of("g", "h", "i"),
            '5', List.of("j", "k", "l"), '6', List.of("m", "n", "o"),
            '7', List.of("p", "q", "r", "s"), '8', List.of("t", "u", "v"),
            '9', List.of("w", "x", "y", "z"));
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result;
        }
        backtrack(digits, new StringBuilder(), result, 0);
        return result;
    }
    private void backtrack(String digits, StringBuilder stringBuilder, List<String> result, int startIndex) {
        if (stringBuilder.length() > digits.length()) {
            return;
        }
        if (stringBuilder.length() == digits.length()) {
            result.add(stringBuilder.toString());
            return;
        }
        for (int i = startIndex; i < digits.length(); i++) {
            char c = digits.charAt(i);
            List<String> options = KEY_MAP.get(c);
            for (String option : options) {
                stringBuilder.append(option);
                backtrack(digits, stringBuilder, result, i + 1);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String digits = scanner.nextLine();
        List<String> result = new LeetCode17().letterCombinations(digits);
        System.out.println("result = " + result);
    }
}