39. 组合总和
题目链接：39. 组合总和 - 力扣（LeetCode）
思路
既然题目说可以数组中的数可以无限制重复被选取，那么说明在选取该元素的下一个分支也可以继续使用。
选取和剪枝过程如图：
注意：为什么取了2以后，剩余元素为5，3。因为如果剩余元素为2，5，3的话在后续操作中会出现重复值的情况，不符合题意。
代码
1 // 剪枝优化
2 class Solution {
3 public List<List<Integer>> combinationSum(int[] candidates, int target) {
4 List<List<Integer>> res = new ArrayList<>();
5 Arrays.sort(candidates); // 先进行排序
6 backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
7 return res;
8 }
9
10 public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
11 // 找到了数字和为 target 的组合
12 if (sum == target) {
13 res.add(new ArrayList<>(path));
14 return;
15 }
16
17 for (int i = idx; i < candidates.length; i++) {
18 // 如果 sum + candidates[i] > target 就终止遍历
19 if (sum + candidates[i] > target) break;
20 path.add(candidates[i]);
21 backtracking(res, path, candidates, target, sum + candidates[i], i);
22 path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
23 }
24 }
25 }
40.组合总和II
题目链接：40. 组合总和 II - 力扣（LeetCode）
思路
这道题和上题思路差不多，不过在本题中存在重复数字，需要去重操作。
如果用map或者caontains函数去重会超时。
本题主要的麻烦是去重问题，而本题去重又分为树层去重（横向）和树枝去重（纵向），而在这道题中，我们只需要对树层去重，这时要注意要先对数组进行排序，目的是为了让相等的元素相邻在一起。 树层去重的方式 如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：元素相同且前一个树枝，使用了candidates[i - 1]，
也就是说同一树层使用过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，说明是进入下一层递归，去下一个数，所以是树枝上去重，这道题树枝是不需要去重的。
代码
1 // 使用used数组
2 class Solution {
3 LinkedList<Integer> path = new LinkedList<>();
4 List<List<Integer>> ans = new ArrayList<>();
5 boolean[] used;
6 int sum = 0;
7
8 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
9 used = new boolean[candidates.length];
10 // 加标志数组，用来辅助判断同层节点是否已经遍历
11 Arrays.fill(used, false);
12 // 为了将重复的数字都放到一起，所以先进行排序
13 Arrays.sort(candidates);
14 backTracking(candidates, target, 0);
15 return ans;
16 }
17
18 private void backTracking(int[] candidates, int target, int startIndex) {
19 if (sum == target) {
20 ans.add(new ArrayList(path));
21 }
22 for (int i = startIndex; i < candidates.length; i++) {
23 if (sum + candidates[i] > target) {
24 break;
25 }
26 // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
27 if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
28 continue;
29 }
30 used[i] = true;
31 sum += candidates[i];
32 path.add(candidates[i]);
33 // 每个节点仅能选择一次，所以从下一位开始
34 backTracking(candidates, target, i + 1);
35 used[i] = false;
36 sum -= candidates[i];
37 path.removeLast();
38 }
39 }
40 }
1 // 不使用标记数组，用idx代替
2 class Solution {
3 List<List<Integer>> res = new ArrayList<>();
4 LinkedList<Integer> path = new LinkedList<>();
5 int sum = 0;
6
7 public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
8 //为了将重复的数字都放到一起，所以先进行排序
9 Arrays.sort( candidates );
10 backTracking( candidates, target, 0 );
11 return res;
12 }
13
14 private void backTracking( int[] candidates, int target, int start ) {
15 if ( sum == target ) {
16 res.add( new ArrayList<>( path ) );
17 return;
18 }
19 for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
20 //正确剔除重复解的办法
21 //跳过同一树层使用过的元素
22 if ( i > start && candidates[i] == candidates[i - 1] ) {
23 continue;
24 }
25
26 sum += candidates[i];
27 path.add( candidates[i] );
28 // i+1 代表当前组内元素只选取一次
29 backTracking( candidates, target, i + 1 );
30
31 int temp = path.getLast();
32 sum -= temp;
33 path.removeLast();
34 }
35 }
36 }
131.分割回文串
题目链接：131. 分割回文串 - 力扣（LeetCode）
思路
这道题有几个难点需要解决
1、切割问题可以抽象为组合问题
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
如图。
2、如何模拟那些切割线
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
3、切割问题中递归如何终止
从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。
4、在递归循环中如何截取子串
需要截取的子串startIndex开始到i，[i, j]的区间范围是一个回文串，即找到截取位置的方法是从startIndex出发找到一个最近的回文串。
5、如何判断回文
可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
代码
1 class Solution {
2 List<List<String>> lists = new ArrayList<>();
3 Deque<String> deque = new LinkedList<>();
4
5 public List<List<String>> partition(String s) {
6 backTracking(s, 0);
7 return lists;
8 }
9
10 private void backTracking(String s, int startIndex) {
11 //如果起始位置大于s的大小，说明找到了一组分割方案
12 if (startIndex >= s.length()) {
13 lists.add(new ArrayList(deque));
14 return;
15 }
16 for (int i = startIndex; i < s.length(); i++) {
17 //如果是回文子串，则记录
18 // 无需在终止地方进行判断，可以一边判断一边加入
19 if (isPalindrome(s, startIndex, i)) {
20 String str = s.substring(startIndex, i + 1);
21 deque.addLast(str);
22 } else {
23 continue;
24 }
25 //起始位置后移，保证不重复
26 backTracking(s, i + 1);
27 deque.removeLast();
28 }
29 }
30 //判断是否是回文串
31 private boolean isPalindrome(String s, int startIndex, int end) {
32 for (int i = startIndex, j = end; i < j; i++, j--) {
33 if (s.charAt(i) != s.charAt(j)) {
34 return false;
35 }
36 }
37 return true;
38 }
39 }
标签：target,组合,int,sum,随想录,candidates,new,path,总和 From： https://www.cnblogs.com/xpp3/p/17162358.html