算法|组合总和 III、17\. 电话号码的字母组合

一、 216. 组合总和 III

题目连接：https://leetcode.cn/problems/combination-sum-iii/
思路：回溯法

class Solution {
    private List<Integer> paths;
    private List<List<Integer>> result;
    private void backTracking(int k, int n, int startIndex, int sum) {
        //剪枝
        if (sum > n) return;
        if (paths.size() == k){
            //收集结果
            if (sum == n) {
                result.add(new ArrayList<>(paths));
            }
            return;
        }
        for (int i = startIndex; i <= 9 - (k - paths.size()) + 1; i++){
            paths.add(i);
            sum += i;
            backTracking(k, n, i + 1, sum);
            paths.remove(paths.size() - 1);
            sum -= i;
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        paths = new ArrayList<>();
        result = new ArrayList<>();
        backTracking(k, n, 1, 0);
        return result;
    }
}

二、 17. 电话号码的字母组合

题目连接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

class Solution {
    private List<String> result;
    private StringBuilder paths;
    private String[] nums;;
    private void backTracking(String digits, int index) {
        if (index == digits.length()) {
            //收集结果
            result.add(paths.toString());
            return;
        }
        String letter = nums[digits.charAt(index) - '0'];
        for (int i = 0; i < letter.length(); i++){
            paths.append(letter.charAt(i));
            backTracking(digits, index + 1);
            paths.deleteCharAt(paths.length() - 1);
        }
    }
    public List<String> letterCombinations(String digits) {
        nums = new String[10];
        nums[2] = "abc";
        nums[3] = "def";
        nums[4] = "ghi";
        nums[5] = "jkl";
        nums[6] = "mno";
        nums[7] = "pqrs";
        nums[8] = "tuv";
        nums[9] = "wxyz";
        result = new ArrayList<>();
        paths = new StringBuilder();
        if (digits != null && !"".equals(digits))
            backTracking(digits, 0);
        return result;
    }
}