算法训练（leetcode）二刷第十九天 | *39. 组合总和、*40. 组合总和 II、*131. 分割回文串

*39. 组合总和

leetcode题目地址

元素可以重复，但结果不可以重复，此题与216. 组合总和 III的思路相似，只是，216. 组合总和 III不可重复使用数字。

不可重复使用，则在回溯算法下一次递归时就从下一个位置开始计算。
可以重复使用，则在回溯算法下一次递归时仍然从当前位置开始计算。

时间复杂度： $O(n\ast 2^n)$
空间复杂度： $O(n)$

// java
class Solution {private int sum = 0;private List<Integer> path = new LinkedList<>();private List<List<Integer>> result = new ArrayList<>();public void backtracing(int[] candidates, int target, int startIdx){if(startIdx >= candidates.length) return;if(sum > target) return;if(sum == target){result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<candidates.length; i++){// 剪枝if(sum>=target) return;path.add(candidates[i]);sum += candidates[i];backtracing(candidates, target, i);sum -= candidates[i];path.removeLast();}}public List<List<Integer>> combinationSum(int[] candidates, int target) {// 排序Arrays.sort(candidates);backtracing(candidates, target, 0);return result;}
}

*40. 组合总和 II

leetcode题目地址

本题难点在于去重。数组中有重复数字，但不可以有重复组合。

因此需要先对数组排序，排序后在同一层递归中相同的数字只进行一次。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {private int sum = 0;private List<Integer> path = new LinkedList<>();private List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] candidates, int target, int startIdx){if(sum > target) return;if(sum == target){result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<candidates.length; i++){// 去重 本层循环已使用相同元素if(i>startIdx && candidates[i] == candidates[i-1]) continue;if(sum >= target) return;sum += candidates[i];path.add(candidates[i]);backtracking(candidates, target, i+1);sum -= candidates[i];path.removeLast();}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, target, 0);return result;}
}

*131. 分割回文串

leetcode题目地址

这里需要注意记录字符串每次递归都需要新创建一个空串，而不是接着上一层接着拼接。

时间复杂度： $O(n\ast 2^n)$
空间复杂度： $O(n^2)$

// java
class Solution {private List<String> path = new LinkedList<>();private List<List<String>> result = new ArrayList<>();public boolean isPalindrome(StringBuilder s){for(int i=0; i<=s.length()/2; i++){if(s.charAt(i) != s.charAt(s.length()-1-i)){return false;}}return true;}public void backtracing(String s, int startIdx, StringBuilder sb){if(startIdx >= s.length()) {result.add(new ArrayList<>(path));return;}for(int i=startIdx; i<s.length(); i++){sb.append(s.charAt(i));    if(isPalindrome(sb)){path.add(sb.toString());backtracing(s, i+1, sb);path.removeLast();}}}public List<List<String>> partition(String s) {backtracing(s, 0, new StringBuilder());return result;}
}