day25

1、leetcode216 组合总和Ⅲ

class Solution {
    List<Integer> path = new LinkedList<Integer>();// 符合条件的结果
    List<List<Integer>> res = new ArrayList<>();// 存放结果集
    int sum;

    public void backTracking(int k, int n, int startIndex) {
        if(path.size() == k) {
            if( sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;// 如果path.size() == k 但sum != targetSum 直接返回
        }

        for(int i=startIndex; i<= 9- (k - path.size()) + 1; i++) {//优化
            sum += i;// 处理
            path.add(i);// 处理
            backTracking(k, n, i+1);// 注意i+1调整startIndex
            sum -= i;// 回溯
            path.remove(path.size()-1);// 回溯
        }

    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return res;
    }
}

2、leetcode17 电话号码的字母组合

class Solution {
    List<String> res = new ArrayList<String>();
    String[] NUMSTRING = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public void backTracking(String digits, StringBuilder sb, int startIndex) {
        if(sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }

        for(int i=startIndex; i<digits.length(); i++) {
            int digit = digits.charAt(i) - '0';
            for(char ch : NUMSTRING[digit].toCharArray()) {
                sb.append(ch);
                backTracking(digits, sb, i+1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return res;
        }

        backTracking(digits, new StringBuilder(), 0);
        return res;
    }
}