代码随想录 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);    }}