day28 回溯

• 39. 组合总和
  • 数字可以被无限制选取，但是无需考虑顺序（组合），因此递归还是需要考虑startIdx，但是每次都从最开始进行回溯，而不是startIdx + 1

• 40.组合总和II
  • ​​​​​​​通过标识去除重复值（树层去重）

• 131.分割回文串
  • ​​​​​​​每次找到切割点，进行向后寻找回文，合适的加入list，不合适直接进入下一层循环

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description:
 *
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 *
 * 可以无限次使用，无需使用startIdx
 *
 */
public class LeetCode39 {
    LinkedList<Integer> sub = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        helper(candidates, target, 0, 0);
        return res;
    }

    private void helper(int[] candidates, int target, int sum, int startIdx) {
        if(sum == target){
            res.add(new ArrayList<>(sub));
            return;
        }

        for(int i = startIdx;i < candidates.length;i++){
            sub.add(candidates[i]);
            sum += candidates[i];
            helper(candidates, target, sum, i);
            sum -= candidates[i];
            sub.removeLast();
        }
    }

}

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description:
 *
 * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 * candidates中的每个数字在每个组合中只能使用一次。
 * 注意：解集不能包含重复的组合。
 *
 * 使用重复数，保证在同一树层上去重
 */
public class LeetCode40 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> sub = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //对同一树层排序，先全体排序
        if(null == candidates || candidates.length == 0){
            return res;
        }

        boolean[] used = new boolean[candidates.length];
        Arrays.sort(candidates);
        helper(candidates, target, 0, used);
        return res;
    }

    public void helper(int[] candidates, int target, int startIdx, boolean[] used){
        if(target < 0){
            return;
        }

        if(target == 0){
            res.add(new ArrayList<>(sub));
            return;
        }


        for(int i = startIdx;i < candidates.length;i++){
            //开始进行树层去重 这里used[i - 1] == false 表示对回溯上来的结果进行判断
            if(i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]){
                continue;
            }

            used[i] = true;
            sub.add(candidates[i]);
            helper(candidates, target - candidates[i], i + 1, used);
            sub.removeLast();
            used[i] = false;
        }

    }
}

package algor.trainingcamp;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhe
 * @version 1.0
 * @description:
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 * 回文串 是正着读和反着读都一样的字符串。
 * @date 2023/5/1 10:22
 */
public class LeetCode131 {
    LinkedList<String> sub = new LinkedList<>();
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if(null == s || s.length() == 0){
            return res;
        }

        helper(s, 0);
        return res;
    }

    public void helper(String s, int startIdx){
        if(startIdx >= s.length()){
            res.add(new ArrayList<>(sub));
            return;
        }

        for(int i = startIdx;i < s.length();i++){
            //如果是回文
            if(isPartition(s, startIdx, i)){
                //【startIdx, i】
                String str = s.substring(startIdx, i + 1);
                sub.add(str);
            }else{
                continue;
            }

            helper(s, i + 1);
            sub.removeLast();
        }

    }

    public boolean isPartition(String s, int start, int end){
        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}