代码随想录算法训练营| 39. 组合总和 、 40.组合总和II 、 131.分割回文串

39. 组合总和 

题目

参考文章

思路：这题的思路其实和上一题的组合总和|||思路差不多，只是这里的元素是可以重复使用的，所以这里的剪枝操作也和上一题组合总和|||有点不一样，以及传入参数中startIndex（idx）的值变化了之外，其他的代码是差不多的。首先先排序，是为了后面剪枝方便，然后res存储结果集，path存储组合，candidates是排序后的数组，sum是总和，startIndex（idx）就是当前要遍历的数组的位置

代码：

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates); // 先进行排序，这里排序后，是为了方便后面剪枝操作，这里进行了排序，后面进行+运算时，可以判断当前和是否大于target，如果大于则后面的元素就可以不用遍历了，直接返回即可backtracking(res, new ArrayList<>(), candidates, target, 0, 0);return res;}public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {// 找到了数字和为 target 的组合if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历//剪枝if (sum + candidates[i] > target) break;path.add(candidates[i]);backtracking(res, path, candidates, target, sum + candidates[i], i);//这里传入的是i，上一题组合总和问题中传的是i+1，这里传入i是因为这里的元素是可以重复使用的，所以递归到下一层的时候，还是从当前位置开始path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素}}
}

40.组合总和II

题目
参考文章

思路：

这道题和之前做的总和题都有点不一样，这题里面数组中有重复元素，而且每个元素也是只能使用一次，这里去重以及遇到重复元素时的判断都是至关重要的。

（重点理解）这里重复元素中，在层遍历中，我们用start进行判断是否在同一层，然后因为包含重复元素，例如都出现 1  1 这种情况，在同一层上，第一个1和后面的元素进行组合，与第二个1与后面的元素进行组合，得到的组合情况是一样的，所以会造成组合重复的情况，所以当重复元素出现，而且在同一层的情况下，就直接跳过。这里同一层的意思就在同一级上，按树状图的形式，每往下就是一层。

其他的方式就是和之前组合题目的方式一样的

代码：

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int sum = 0;public List<List<Integer>> combinationSum2( int[] candidates, int target ) {//为了将重复的数字都放到一起，所以先进行排序Arrays.sort( candidates );backTracking( candidates, target, 0 );return res;}private void backTracking( int[] candidates, int target, int start ) {if ( sum == target ) {res.add( new ArrayList<>( path ) );return;}for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {//正确剔除重复解的办法//跳过同一树层使用过的元素//因为前面对数组进行了排序，所以当前一个元素和后一个元素相等时，而且是在同一层的情况下，就直接跳过，判断同一层的就是i>start，这个比较就是判断是否在同一层上if ( i > start && candidates[i] == candidates[i - 1] ) {continue;}sum += candidates[i];path.add( candidates[i] );// i+1 代表当前组内元素只选取一次backTracking( candidates, target, i + 1 );int temp = path.getLast();sum -= temp;path.removeLast();}}
}

 131.分割回文串 

题目

参考文章

思路：这题其实和之前题目思路差不多，只是这里是分割字符串，把分割好的字符串存储到一个StringBuilder中，判断其是否是回文子串，如果是回文串才进行下一步的递归

代码：

class Solution {//保持前几题一贯的格式， initializationList<List<String>> res = new ArrayList<>();List<String> cur = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0, new StringBuilder());return res;}private void backtracking(String s, int start, StringBuilder sb){//因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的if (start == s.length()){//注意创建一个新的copyres.add(new ArrayList<>(cur));return;}//像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位for (int i = start; i < s.length(); i++){sb.append(s.charAt(i));if (check(sb)){//判断回文，这里判断回文，每往下递归都是只有一个元素，只有在同一层的情况下才会出现两个元素cur.add(sb.toString());backtracking(s, i + 1, new StringBuilder());cur.remove(cur.size() -1 );}}}//helper method, 检查是否是回文private boolean check(StringBuilder sb){for (int i = 0; i < sb.length()/ 2; i++){if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}}return true;}
}