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

本文主要是介绍代码随想录算法训练营第27天|● 39. 组合总和● 40.组合总和II● 131.分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

组合总和

题目链接

39. 组合总和 - 力扣（LeetCode）

代码：

class Solution {public  List<List<Integer>> res = new ArrayList<>();public  List<Integer> list = new ArrayList<>();public  int sum = 0;/*** @param nums    目标数组* @param target  目标和* @param start   起始位置*/public  void dfs(int[] nums, int target, int start) {//sum>=target就返回if (sum > target) {return;}if (sum == target) {res.add(new ArrayList<>(list));return;}for (int i = start; i < nums.length; i++) {list.add(nums[i]);//处理sum += nums[i];dfs(nums, target, i);//递归，注意这里是i（表示可以重复读取当前的数）list.remove(list.size() - 1);//回溯sum -= nums[i];}}public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates, target, 0);return res;}
}

组合总和II

题目链接

40. 组合总和 II - 力扣（LeetCode）

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

需要对同一层上的用过的数进行去重

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

这块比较抽象，如图：

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过

可能有的录友想，为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：

代码：

class Solution {public  List<List<Integer>> res = new ArrayList<>();public  List<Integer> list = new ArrayList<>();public  int sum = 0;/*** @param nums   目标数组* @param target 目标和* @param start  起始位置*/public  void dfs(int[] nums, int target, int start) {//sum>=target就返回if (sum > target) {return;}if (sum == target) {res.add(new ArrayList<>(list));return;}for (int i = start; i < nums.length; i++) {if ( i > start && nums[i] == nums[i - 1] ) {//同一层不能重复取continue;}list.add(nums[i]);//处理sum += nums[i];dfs(nums, target, i + 1);//递归int temp=list.get(list.size()-1);sum-=temp;list.remove(list.size() - 1);//回溯}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);dfs(candidates, target, 0);return res;}
}

分割回文串

题目链接

131. 分割回文串 - 力扣（LeetCode）

利用回溯处理切割问题，

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

代码:

class Solution {public List<List<String>>  res=new ArrayList<>();public  List<String> list=new ArrayList<>();public  boolean cheak(String s,int start,int end){for (int i = start,j=end; i <j ; i++,j--) {if(s.charAt(i)!=s.charAt(j)){return false;}}return true;}public  void dfs(String s,int startIndex) {if (startIndex >= s.length()) {res.add(new ArrayList(list));return;}for (int i = startIndex; i < s.length(); i++) {//如果是回文子串，则记录if (cheak(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);list.add(str);} else {continue;}//起始位置后移，保证不重复dfs(s, i + 1);list.remove(list.size() - 1);}}public List<List<String>> partition(String s) {dfs(s, 0);return res;}
}

这篇关于代码随想录算法训练营第27天|● 39. 组合总和● 40.组合总和II● 131.分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---