学习任务：
- 39. 组合总和
- 40.组合总和II
- 131.分割回文串
Leetcode39. 组合总和
难度：中等 | 相关标签：数组、回溯
-
题目： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。 -
思路： 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
-
注意：
- 可以无限重复，但是有总和的限制，所以间接的也是有个数的限制
-
代码：
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序backtracking(candidates, target, 0, 0);return res;}public void backtracking( int[] candidates, int target, int sum, int idx) {if(sum > target){return;}if(sum == target){res.add(new ArrayList<>(path));return;}for(int i = idx; i < candidates.length ; i++){path.add(candidates[i]);sum = sum + candidates[i];backtracking(candidates, target, sum, i);sum = sum- candidates[i];path.removeLast();}}
}
- 反思：
Leetcode40.组合总和II
难度：中等 | 相关标签：数组、回溯
-
题目： 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 -
思路：
-
注意：
- 本题candidates 中的每个数字在每个组合中只能使用一次。
- 本题数组candidates的元素是有重复的，而39.组合总和 是无重复元素的数组candidates
- 需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。
-
代码：
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();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 res;}public void backtracking( int[] candidates, int target, int sum, int idx) {if(sum > target){return;}if(sum == target){res.add(new ArrayList<>(path));return;}for(int i = idx; i < candidates.length ; i++){// 树层去重 !!!if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false){continue;}used[i] = true;path.add(candidates[i]);sum = sum + candidates[i];backtracking(candidates, target, sum, i+1);sum = sum - candidates[i];path.removeLast();used[i] = false;}}
}
- 反思：
Leetcode131.分割回文串
难度：中等 | 相关标签：，
-
题目： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串 。返回 s 所有可能的分割方案。 -
思路：
- 切割问题，有不同的切割方式
- 判断回文
-
注意：
-
代码：
class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return res;}public void backtracking(String s, int idx) {if(idx >= s.length()){res.add(new ArrayList<>(path));return;}for(int i = idx; i < s.length() ; i++){// 判断子串是否回文，是就记录if(isPalindrome(s, idx, i)){String str = s.substring(idx, i + 1);path.add(str);}else{continue;}backtracking(s, i+1);path.removeLast();}}//判断是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {for (int i = startIndex, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}- 反思：