低价网站建设教程,做网站要会哪些软件,中建卓越建设管理有限公司网站,专业公司网站开发服务39. 组合总和
思路
题目中的无限制重复被选取#xff0c;提示#xff1a;1 candidates[i] 200。
本题和77.组合 (opens new window)#xff0c;216.组合总和III (opens new window)的区别是#xff1a;本题没有数量要求#xff0c;可以无限重复#xff0c;但…39. 组合总和
思路
题目中的无限制重复被选取提示1 candidates[i] 200。
本题和77.组合 (opens new window)216.组合总和III (opens new window)的区别是本题没有数量要求可以无限重复但是有总和的限制所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下 注意图中叶子节点的返回条件因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回
回溯三部曲
递归函数参数
这里依然是定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。
首先是题目中给出的参数集合candidates, 和目标值target。
target做相应的减法就可以了最后如果 target0 就说明找到符合的结果了。
本题还需要startIndex来控制for循环的起始位置对于组合问题什么时候需要startIndex呢
卡哥举过例子如果是一个集合来求组合的话就需要startIndex例如77.组合 (opens new window)216.组合总和III (opens new window)。
如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例如17.电话号码的字母组合(opens new window)
注意以上只是说求组合的情况如果是排列问题又是另一套分析的套路后面我在讲解排列的时候会重点介绍。
代码如下
//结果集
ListListInteger res new ArrayList();
//记录路径
ListInteger path new ArrayList();
void backtracking(int[] candidates, int target,int startIndex)
递归终止条件
在如下树形结构中 从叶子节点可以清晰看到终止只有两种情况sum大于target等于target。
sum等于target的时候需要收集结果代码如下
if (target 0){// 找到了数字和为 target 的组合res.add(new ArrayList(path));return;
}
if (target 0){return;
}
单层搜索的逻辑
单层for循环依然是从startIndex开始搜索candidates集合。
注意本题和77.组合 (opens new window)、216.组合总和III (opens new window)的一个区别是本题元素为可重复选取的。
如何重复选取呢看代码注释部分
for (int i startIndex; i candidates.length; i) {if(target-candidates[i] 0){break;}// 如果 sum candidates[i] target 就终止遍历path.add(candidates[i]);backtracking(candidates,target-candidates[i],i);path.remove(path.size() - 1);// 回溯移除路径 path 最后一个元素
}#剪枝优化
在这个树形结构中 以及上面的版本一的代码可以看到对于sum已经大于target的情况其实是依然进入了下一层递归只是下一层递归结束判断的时候会判断sum target的话就返回。
其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。
对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。
如图 for循环剪枝代码如下
if(target-candidates[i] 0){break;}// 如果 sum candidates[i] target 就终止遍历
整体代码如下注意注释的部分
class Solution {//结果集ListListInteger res new ArrayList();//记录路径ListInteger path new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序,利于之后递归循环进行剪枝操作backtracking(candidates,target,0);return res;}void backtracking(int[] candidates, int target,int startIndex){if (target 0){// 找到了数字和为 target 的组合res.add(new ArrayList(path));return;}if (target 0){return;}for (int i startIndex; i candidates.length; i) {if(target-candidates[i] 0){break;}// 如果 sum candidates[i] target 就终止遍历path.add(candidates[i]);backtracking(candidates,target-candidates[i],i);path.remove(path.size() - 1);// 回溯移除路径 path 最后一个元素}}
} 40.组合总和II 思路
这道题目和39.组合总和 (opens new window)如下区别
本题candidates 中的每个数字在每个组合中只能使用一次。本题数组candidates的元素是有重复的而39.组合总和 (opens new window)是无重复元素的数组candidates
最后本题和39.组合总和 (opens new window)要求一样解集不能包含重复的组合。
本题的难点在于区别2中集合数组candidates有重复元素但还不能有重复的组合。
用set或者map去重这么做很容易超时
所以要在搜索的过程中就去掉重复组合。
这个去重为什么很难理解呢所谓去重其实就是使用过的元素不能重复选取。
都知道组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成没有彻底理解去重的根本原因。
那么问题来了我们是要同一树层上使用过还是同一树枝上使用过呢
回看一下题目元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。
整体代码如下
class Solution {//结果集ListListInteger res new ArrayList();//记录路径ListInteger path new ArrayList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);//为了将重复的数字都放到一起所以先进行排序backtracking(candidates,target,0);return res;}void backtracking(int[] candidates, int target,int startIndex){if (target0){return;}if (target 0){res.add(new ArrayList(path));return;}for (int i startIndex; i candidates.length; i) {if (target - candidates[i] 0){break;}//正确剔除重复解的办法//跳过同一树层使用过的元素if(i startIndex candidates[i] candidates[i-1]){continue;}path.add(candidates[i]);backtracking(candidates,target-candidates[i],i1);path.remove(path.size() - 1);}}
}
在上述中卡哥说的使用一个used数据来标记该结点是否被使用过了。理解起来稍微有点抽象但其实也可以不用 used 数组标记只需要通过
if(i startIndex candidates[i] candidates[i-1]){continue;
}
来判断是否使用过该结点。具体的还是需要加深理解具体见代码。 131.分割回文串
思路
本题这涉及到两个关键问题
切割问题有不同的切割方式判断回文
回溯究竟是如何切割字符串呢
我们来分析一下切割其实切割问题类似组合问题。
例如对于字符串abcdef
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段.....。
所以切割问题也可以抽象为一棵树形结构如图 对于每一层遍历先切割单个单个的字符切割完成后判断 startIndex 是否 给出的字符串长度为true则结束当前递归然后在逐渐切割多个。 递归用来纵向遍历for循环用来横向遍历切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。
此时可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
#回溯三部曲
递归函数参数
全局变量数组path存放切割后回文的子串二维数组result存放结果集。
本题递归函数参数还需要 startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。
代码如下
ListListString res new ArrayList();
LinkedListString path new LinkedList();// 放已经回文的子串
void backtracking(String s,int startIndex)递归函数终止条件 从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。
那么在代码里什么是切割线呢
在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。
所以终止条件代码如下
// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了
if (startIndex s.length()){res.add(new ArrayList(path));return;
}单层搜索的逻辑
来看看在递归循环中如何截取子串呢
在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文如果是回文就加入在 LinkedListString path 中path用来记录切割过的回文子串。
代码如下
for (int i startIndex; i s.length(); i) {if (!isPalindrome(s,startIndex,i)){//如果当前不是回文子串continue;// 如果不是则直接跳过}//如果是回文子串// 获取[startIndex,i1)在s中的子path.add(s.substring(startIndex,i1));//字符串截取是左闭右开的backtracking(s,i1);// 寻找i1为起始位置的子串path.removeLast();// 回溯过程弹出本次已经添加的子串
}
注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。
#判断回文子串
最后我们看一下回文子串要如何判断了判断一个字符串是否是回文。
可以使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了。
那么判断回文的C代码如下
boolean isPalindrome(String str,int left,int right){for (int i left,j right; i j; i,j--) {if (str.charAt(i) ! str.charAt(j)){return false;}}return true;
}
整体代码如下注释:
class Solution {ListListString res new ArrayList();LinkedListString path new LinkedList();public ListListString partition(String s) {backtracking(s,0);return res;}void backtracking(String s,int startIndex){// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.length()){res.add(new ArrayList(path));return;}for (int i startIndex; i s.length(); i) {if (!isPalindrome(s,startIndex,i)){//如果当前不是回文子串continue;// 如果不是则直接跳过}//如果是回文子串// 获取[startIndex,i1)在s中的子path.add(s.substring(startIndex,i1));//字符串截取是左闭右开的backtracking(s,i1);// 寻找i1为起始位置的子串path.removeLast();// 回溯过程弹出本次已经添加的子串}}boolean isPalindrome(String str,int left,int right){for (int i left,j right; i j; i,j--) {if (str.charAt(i) ! str.charAt(j)){return false;}}return true;}
} 以上为我做题时候的相关思路自己的语言组织能力较弱很多都是直接抄卡哥的有错误望指正。
