LeetCode算法题解（回溯）|LeetCode216. 组合总和 III、LeetCode17. 电话号码的字母组合

一、|LeetCode216. 组合总和 III

题目链接：216. 组合总和 III

题目描述：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

2 <= k <= 9
1 <= n <= 60

算法分析：

利用回溯算法，首先创建一个二维数组来存放所有合理组合的结果集，用一个一维数组来搜索所有组合。

然后通过递归来纵向遍历组合里的每个元素。

递归参数：每个元素开始的位置坐标startInt，组合中的所有元素总和。

递归结束条件：如果组合的长度等于规定长度K，无论组合总和是否等于N都要返回。

然后用for循环横向遍历从startInt开始到9，

每层for循环，将对应元素i插入组合，同时总和sum也要加上i，然后递归下一层。

递归之后就是回溯，要将当前的元素i从组合中拿出来，sum也要减掉i，再进行下一层for循环。

代码如下：

class Solution {List<List<Integer>>result = new ArrayList<>();//用来存放所有组合的结果集LinkedList<Integer>path = new LinkedList<>();//用来寻找每种合理组合int K;int N;public void backTraving(int startInt, int sum) {//递归纵向遍历组合的每个元素if(path.size() == K) {//如果组合长度等于K，无论组合总和是否等于n都要推出递归if(sum == N) result.add(new LinkedList(path));//如果组合总和等于n就将组合放入结果集然后返回return;}for(int i = startInt; i <=9; i++) {//for循环横向遍历1~9path.add(i);sum += i;backTraving(i + 1, sum);//递归//回溯sum -= i;path.removeLast();}}public List<List<Integer>> combinationSum3(int k, int n) {K = k;N = n;backTraving(1, 0);return result;}
}

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

题目链接：17. 电话号码的字母组合

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

算法分析：

利用回溯算法。

递归纵向遍历字符串digits的每个数字字符。

传递参数：当前组合的长度；

递归结束条件：如果当前组合长度等于digits的长度，将组合放入结果集然后返回。

然后横向遍历每个数字字符所映射的每个字符，将字符依次插入组合，后递归，再删除。

代码如下：

class Solution {List<String>result = new ArrayList<String>();//用来存放结果集StringBuilder path = new StringBuilder();//用来搜索所有组合int len;//字符串长度public void backTraving(String digits, int index) {//递归纵向遍历字符串每个数字字符if(index == len) {result.add(path.toString());return;}switch(digits.charAt(index)) {//横向遍历每个字符所映射的字符，然后递归回溯case '2':{path.append('a');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('b');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('c');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '3':{path.append('d');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('e');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('f');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '4':{path.append('g');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('h');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('i');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '5':{path.append('j');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('k');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('l');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '6':{path.append('m');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('n');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('o');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '7':{path.append('p');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('q');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('r');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('s');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '8':{path.append('t');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('u');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('v');backTraving(digits, index + 1);path.deleteCharAt(index);break;}case '9':{path.append('w');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('x');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('y');backTraving(digits, index + 1);path.deleteCharAt(index);path.append('z');backTraving(digits, index + 1);path.deleteCharAt(index);break;}default:break;}}public List<String> letterCombinations(String digits) {len = digits.length();if(len == 0) return result;backTraving(digits, 0);return result;}
}