DAY27| 39. 组合总和 ,40.组合总和II ,131.分割回文串

39.组合总和

文字讲解：组合总和

视频讲解：组合总和

状态: 此题ok

思路：

代码：

class Solution {int sum;public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();backTracking(result, tempList, candidates, 0, target);return result;}public void backTracking(List<List<Integer>> result, LinkedList<Integer> tempList, int[] candidates, int startIndex, int target) {if (!tempList.isEmpty()&&sum>target) {return;}if (!tempList.isEmpty() && sum==target) { //收集List<Integer> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < candidates.length; i++) {tempList.offer(candidates[i]);sum+=candidates[i];backTracking(result, tempList, candidates, i, target);tempList.pollLast();sum-=candidates[i];}}
}

40.组合总和II

文字讲解：组合总和II

视频讲解：组合总和II

状态：这题一开始想先排序后去重，再做回溯；想岔批了，应该要保证前后处理相同元素的时候，要进行跳过来进行去重；

思路：

1、这一题，注意枝剪操作，即sum + candidates[i] <= target；不然提交leetcode会超时；

代码：

class Solution {int sum;public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();Arrays.sort(candidates);//完成去重backTracking(result, tempList, candidates, 0, target);return result;}public void backTracking(List<List<Integer>> result, LinkedList<Integer> tempList, int[] candidates, int startIndex, int target) {if (!tempList.isEmpty()&&sum==target) {List<Integer> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {if (i>startIndex && candidates[i]==candidates[i-1]) {continue;}tempList.offer(candidates[i]);sum+=candidates[i];backTracking(result, tempList, candidates, i+1, target);tempList.pollLast();sum-=candidates[i];}}
}

131.分割回文串

文字讲解：分割回文串

视频讲解：分割回文串

状态：这题细细一想，和前两题也是类似换汤不换药，看来还是对回溯-排列问题理解不够透彻；

思路：

代码：

class Solution {List<List<String>> result = new ArrayList<>();LinkedList<String> tempList = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}public void backTracking(String s, int startIndex) {if (startIndex>=s.length()) {List<String> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < s.length(); i++) {if(isPalindrome(s, startIndex, i)) {tempList.offer(s.substring(startIndex, i+1));} else {continue;}backTracking(s, i+1);tempList.pollLast();}}public boolean isPalindrome(String s, int start, int end) {while (start<=end) {if (s.charAt(start) == s.charAt(end)) {start++;end--;} else {return false;}}return true;}
}