代码随想录算法训练营第27天| 39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和

思路：

本题中有一个特殊的条件：同一个数字可以无限制重复被选取。
因此在递归时，startIndex应该是i，而不是i+1

代码

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

再考虑如何剪枝，在调试测试用例[2,3,6,7]时发现，如果集合是递增的，前面的元素如果相加超出范围，那么也就无需考虑后面的元素了，必定也超范围。

因此可以先给集合排序。

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	// 数组排序
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }
    public void backtracking(int[] candidates, int target, int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
        	// 直接跳出循环，第一个 > target的元素及其后面的元素都不遍历
            if(sum+candidates[i] > target) break;
            path.add(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates, target, i);
            sum-=candidates[i];
            path.removeLast();
        }
    }
}

40.组合总和II

思路：

题目要求解集不能包含重复的组合，但是候选数组中如果有重复元素，不加处理就会必定产生重复集合。

一开始的想法是先用set去重，再返回List，会超时。

因此只能在遍历时去重，组合问题可以抽象为树形结构，那么去重在这个树形结构上是有两个维度的，一个维度是同一树枝上去重，一个维度是同一树层上去重。
本题应该是在同一树层上去重，同一树枝上无需去重。

代码

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }
    public void backtracking(int[] candidates, int target, int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum > target) return;
        for (int i = startIndex; i < candidates.length; i++) {
            // 同一树层去重，注意是i>startIndex，如果是i>0，树层和树枝都会去重
            if(i>startIndex && candidates[i] == candidates[i-1]) continue;
            
            path.add(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates, target, i+1);
            sum-=candidates[i];
            path.removeLast();
        }
    }
}

131.分割回文串

思路：

注意分割方法

代码

class Solution {
    //判断是否是回文串
    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;
    }

    public List<List<String>> res = new ArrayList<>();
    public Deque<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }

     private void backtracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backtracking(s, i + 1);
            path.removeLast();
        }
    }
}