Day22
216.组合总和III
力扣题目链接
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
思路
使用全局变量res接收结果集，path不断更新添加删除元素，sum不断累加累减
回溯函数
如果sum大了，直接return；如果size为k且sum为n，加入结果集，之后return
在循环中，不断加入元素，改变sum，回溯return说明不符合要求，要改变sum并弹出元素
代码
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 1);return res;}private void backtracking(int k, int n, int start) {if (sum > n) return;if (path.size() == k){if (sum == n) {res.add(new ArrayList<>(path));}return;}for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {path.addFirst(i);sum += i;backtracking(k, n, i + 1);sum -= i;path.removeFirst();}}
}17.电话号码的字母组合
力扣题目链接
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
思路
首先需要把数字和字符串对应，给出一个字符串数组
编写递归函数，传入一个字符串，全是数字，对他进行处理，输出一个字符串集合；注意还要传入一个index不然没法判断终止条件
终止条件是，如果index和传入字符串长度相等，就加入res中
根据传入的字符串和index，可以拿到一个字符串数组某个位置的字符串，这个字符串提前写好，是全局变量
然后这个题目就变成了，若干个字符串中的字符要进行组合，我们把每个字符串进行循环遍历，不断append，然后递归到下一个字符串，递归结束就删除字符，这样大循环结束之后就完成了字符串中字符组合的操作
代码
class Solution {List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) return res;//简单的直接返回backtracking(digits,0);return res;}private void backtracking(String digits, int index){//使用index标注已经处理的数字个数if (index == digits.length()){//找到符合要求的了res.add(sb.toString());//加入res后返回return;}String str = numString[digits.charAt(index) - '0'];//取出digit某个位置对应的numString字符串元素for (int i = 0; i < str.length(); i++) {//后面其实就是进行若干个字符串的组合sb.append(str.charAt(i));backtracking(digits,index + 1);//注意这里是index+1，因为终止条件判断的是index，每一次递归都是一层循环sb.deleteCharAt(sb.length() - 1);}}
}
