77.组合
题目链接/文章讲解：代码随想录
视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
剪枝操作：带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
代码随想录
回溯基本思路:
剪枝思路：
以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
for (int i = startIndex; i <= n; i++) {
接下来看一下优化过程如下：
-
已经选择的元素个数：path.size();
-
还需要的元素个数为: k - path.size();
-
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
所以优化之后的for循环是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
代码：
class Solution {List<List<Integer>> results = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {getPath(n,k,1);return results;}public void getPath(int n,int k, int startIndex){if(path.size()==k){results.add(new ArrayList<>(path));return;}for(int i = startIndex;i<=n-(k-path.size())+1;i++){path.add(i);getPath(n,k,i+1);path.remove(path.size()-1);}}
}216.组合问题III
题目链接/文章讲解： 代码随想录视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
代码随想录：
已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
那么剪枝的地方可以放在递归函数开始的地方，剪枝代码如下：
if (sum > targetSum) { // 剪枝操作return;
}代码：
class Solution{List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {getPath(n,k,1);return result;}public void getPath (int n,int k,int startIndex){if(path.size()==k){if(sum==n){result.add(new ArrayList<>(path));}return;}for (int i = startIndex; i <= 9-(k-path.size())+1; i++) {sum+=i;path.add(i);if(sum>n){sum-=i;path.remove(path.size()-1);return;}getPath(n,k,i+1);sum-=i;path.remove(path.size()-1);}}
}17.电话号码的字母组合
题目链接/文章讲解：代码随想录
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
代码随想录：
关于字符串为空时：
我的做法是在主函数直接判断字符串为空，那么就返回空结果，不用再进入回溯函数。和示例代码相似：
if (digits == null || digits.length() == 0) {return list;}存储字母编号的数据结构：
//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};我选用的是map是比较恐惧和字符串打交道，但是选用数组与index下标对应更为简洁。
代码
class Solution {List<String> results = new ArrayList<>();StringBuilder path = new StringBuilder();Map map = new HashMap();public List<String> letterCombinations(String digits) {map.put('2', new char[]{'a', 'b', 'c'});map.put('3', new char[]{'d', 'e', 'f'});map.put('4', new char[]{'g', 'h', 'i'});map.put('5', new char[]{'j', 'k', 'l'});map.put('6', new char[]{'m', 'n', 'o'});map.put('7', new char[]{'p', 'q', 'r','s'});map.put('8', new char[]{'t', 'u', 'v'});map.put('9', new char[]{'w', 'x', 'y','z'});char[] charArray = digits.toCharArray();if(charArray.length==0){return results;}getPhoneCombination(charArray,0);return results;}public void getPhoneCombination(char[] digits,int index){if(path.length()==digits.length) {results.add(path.toString());return;}char digit = digits[index];char[] item = (char[]) map.get(digit);for(int i = 0;i<item.length;i++){path.append(item[i]);getPhoneCombination(digits,index+1);path.deleteCharAt(path.length()-1);}}
}
