一、力扣216.组合总和三

1.1 题目

1.2 思路

自己的想法：和总和问题思路类似，回溯法。
（1）k个数的组合，那么就是k层递归+循环；
（2）递归终止条件：path.size() == k,判断path之和是否为n，是则加入res，最后return;
（3）声明成员变量res；path；sum。

根据以下示例的启示：想到剪枝方法。
当path.size()还未达到k时，出现sum >= n，那么可以提前结束遍历。

1.3 代码

无剪枝：

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<Integer> path = new ArrayList<>();public int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backTracking(k,n,1);return res;}public void backTracking(int k,int n,int startIndex){//递归终止条件if(path.size() == k){if(sum == n){res.add(new ArrayList<>(path));}return;}//单层递归逻辑for(int i = startIndex;i<=9;i++){path.add(i);sum += i;backTracking(k,n,i+1);//回溯path.remove(path.size()-1);sum -= i;}}
}

剪枝：

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<Integer> path = new ArrayList<>();public int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backTracking(k,n,1);return res;}public void backTracking(int k,int n,int startIndex){//递归终止条件if(path.size() == k){if(sum == n){res.add(new ArrayList<>(path));}return;}//剪枝if(sum >= n){return;}//单层递归逻辑for(int i = startIndex;i<=9;i++){path.add(i);sum += i;backTracking(k,n,i+1);//回溯path.remove(path.size()-1);sum -= i;}}
}

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

2.1 题目

2.2 思路

思路：和组合问题类似，不过需要设置一个map来存储电话号码数字到字母的映射；

2.3 代码

独立思路，完成代码，虽然调试了很久：

class Solution {public List<String> res = new ArrayList<>();public List<Character> path = new ArrayList<>();public HashMap<Character,String> hashmap = new HashMap<>();public List<String> letterCombinations(String digits) {//处理特殊情况if(digits.length()==0){return res;}//初始化hashmap,存储电话按键与字母的映射hashmap.put('2',"abc");hashmap.put('3',"def");hashmap.put('4',"ghi");hashmap.put('5',"jkl");hashmap.put('6',"mno");hashmap.put('7',"pqrs");hashmap.put('8',"tuv");hashmap.put('9',"wxyz");backTracking(digits,0);return res; }public void backTracking(String digits,int index){//确定递归的终止条件if(index == digits.length()){char[] ch = new char[digits.length()];for(int i=0;i<ch.length;i++){ch[i] = path.get(i);}res.add(String.valueOf(ch));return;}//单层递归逻辑String value =  hashmap.get(digits.charAt(index));for(int i =0;i<value.length();i++){path.add(value.charAt(i));backTracking(digits,index+1);path.remove(path.size()-1);}}
}