算法训练Day27|39. 组合总和● 40.组合总和II● 131.分割回文串

 1class Solution {
 2    public List<List<Integer>> combinationSum(int[] candidates, int target) {
 3        List<List<Integer>> res = new ArrayList<>(); // 存储结果的结果集
 4        Arrays.sort(candidates); // 对其进行排序,便于剪枝操作（优化搜索过程）
 5        backtracking(res, new ArrayList<>(), candidates, target, 0, 0); // 调用递归函数进行回溯搜索
 6        return res;
 7    }
 8
 9    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
10        // 如果当前路径的和等于目标值，将路径加入结果集并返回
11        if (sum == target) {
12            res.add(new ArrayList<>(path));
13            return;
14        }
15        // 遍历数组中的元素
16        for (int i = idx; i < candidates.length; i++) {
17            if (sum + candidates[i] > target) break; // 终止条件：如果当前和大于目标值，剪枝操作
18            path.add(candidates[i]);  // 不大于目标和，则将元素加入路径
19            backtracking(res, path, candidates, target, sum + candidates[i], i); // 递归调用下一个元素
20            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素，寻找新的路径
21        }
22    }
23}

 1class Solution {
 2    LinkedList<Integer> path = new LinkedList<>(); // 存储当前路径的链表
 3    List<List<Integer>> ans = new ArrayList<>(); // 存储所有符合结果的结果集
 4    boolean[] used; // 记录元素是否被使用过的数组
 5    int sum = 0; // 当前路径元素的和
 6
 7    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 8        used = new boolean[candidates.length]; // 初始化used[]数组
 9        Arrays.fill(used,false); // 全部置为false
10        Arrays.sort(candidates); // 将数组candidates[] 排序，便于剪枝操作，优化搜索
11        backtracking(candidates, target, 0); // 调用递归函数进行递归搜索
12        return ans;
13    }
14
15    private void backtracking(int[] candidates, int target, int startIndex) {
16        // 将符合条件的结果加入到结果集中
17        if (sum == target) {
18            ans.add(new ArrayList(path));
19        }
20        // 横向遍历所有元素
21        for (int i = startIndex; i < candidates.length; i++) {
22            // 当前路径元素和大于目标target，剪枝操作
23            if (sum + candidates[i] > target) {
24                break;
25            }
26            // 当前节点大于0且遇到重复元素且上一个元素没有用过，则当前元素与后序存在重复，剪枝操作
27            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
28                continue;
29            }
30            // 符合加入路径条件的
31            used[i] = true; // 记录该元素使用过
32            sum += candidates[i]; // sum加上当前元素
33            path.add(candidates[i]); // 将元素值加入路径
34            // 每个节点仅能选择一次，所以从下一位开始 i + 1
35            // 竖向递归选出符合条件的元素
36            backtracking(candidates, target, i + 1);
37            // 回溯——修改used值——和减去最后一个值——路径减去最后一个元素
38            used[i] = false;
39            sum -=candidates[i];
40            path.removeLast();
41        }
42    }
43}

 1class 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    private void backtracking(String s, int startIndex) {
10        // 遍历到最后位置，startIndex在这里更像是索引
11        if (startIndex >= s.length()) {
12            lists.add(new ArrayList(deque)); // 将结果加入结果集中
13            return;
14        }
15        // 横向遍历字符串
16        for (int i = startIndex; i < s.length(); i++) {
17            // 判断是否是回文字符串
18            if (isPalindrome(s, startIndex, i)) {
19                // 如果是回文串，将其加入到队列中
20                String str = s.substring(startIndex, i + 1);
21                deque.addLast(str);
22            } else {
23                // 不是，则结束本次循环，继续下一次循环
24                continue;
25            }
26            // 递归调用函数，继续搜索下一个回文子串
27            backtracking(s, i + 1);
28            deque.removeLast(); // 回溯 删除队列中最后一个元素，便于加入其他可能的回文子串
29        }
30    }
31    // 判断字符串是否是回文子串
32    private boolean isPalindrome(String s, int startIndex, int end) {
33        // 双指针+for循环遍历
34        for (int i = startIndex, j = end; i < j; i++, j--) {
35            if (s.charAt(i) != s.charAt(j)) {
36                return false;
37            }
38        }
39        return true;
40    }
41}