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);}}
}