day23：回溯part3，继续组合问题

39.组合总和

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return ans;}public void backtracking(int[] candidates, int target, int sum, int startIndex) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (sum > target) break;path.add(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);path.removeLast();sum -= candidates[i];}}
}

40.组合总和 II

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length];Arrays.fill(used, false);Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return ans;}public void backtracking(int[] candidates, int target, int sum, int startIndex) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (sum > target) break;// 判断是树层上重复还是树枝上重复，树层上重复才需去重，回溯回来used数组前一位应为falseif (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;path.add(candidates[i]);sum += candidates[i];used[i] = true;backtracking(candidates, target, sum, i + 1);path.removeLast();sum -= candidates[i];used[i] = false;}}
}

131.分割回文串

class Solution {List<List<String>> ans = new ArrayList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return ans;}private void backtracking(String s, int startIndex) {if (startIndex >= s.length()) {ans.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s, startIndex, i))path.add(s.substring(startIndex, i + 1));else continue;backtracking(s, i + 1);path.removeLast();}}private boolean isPalindrome(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;}
}