代码随想录第22天|回溯算法

77.组合

题目链接/文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili

剪枝操作：带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili

 代码随想录

回溯基本思路:

 剪枝思路：

以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

for (int i = startIndex; i <= n; i++) {

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合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);}}
}