216.组合总和III 17.电话号码的字母组合

216.组合总和III

回溯的常规思路做这道题：

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    LinkedList<Integer> res = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        f(k,n,1);
        return list;
        
    }
    void f(int k,int n,int startIndex){
        if(res.size() == k){
            if(n == 0) list.add(new ArrayList(res));
            return;
        }
        for(int i = startIndex;i <= 9 - (k - res.size()) + 1;i++){
            res.add(i);
           f(k,n - i,i + 1);
            res.removeLast();
        }
    }
}

17.电话号码的字母组合

class Solution {
    List<String> list;
    public List<String> letterCombinations(String digits) {
        list = new ArrayList<>();
        if(digits == null || digits.length() == 0) return list;
        
        String[] s = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(digits,0,s);
        return list;
    }
    StringBuilder sb = new StringBuilder();
    void dfs(String digits,int idx,String[] s){
        if(idx == digits.length()){
            list.add(sb.toString());
            return;
        }
        //这行代码很关键，递归遍历字符串
        String str = s[digits.charAt(idx) - '0'];
        for(int i = 0;i < str.length();i++){
            sb.append(str.charAt(i));
            dfs(digits,idx + 1,s);
            sb.deleteCharAt(sb.length() - 1);
        }
        
    }
}