代码学习记录22--回溯算法第三天

随想录日记part22

$t im e ：$ 2024.03.17

主要内容：今天主要是结合类型的题目加深对回溯算法的理解：1.组合总和;2.组合总和
;3.分割回文串。

39. 组合总和
40.组合总和II
131.分割回文串

Topic1组合总和

题目：

给你一个无重复元素的整数数组 $c an d i d a t es$ 和一个目标整数 $t a r g e t$ ，找出 $c an d i d a t es$ 中可以使数字和为目标数 $t a r g e t$ 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
$c an d i d a t es$ 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 $t a r g e t$ 的不同组合数少于 150 个。

输入： $c an d i d a t es = [2, 3, 6, 7], t a r g e t = 7$
输出： $[[2, 2, 3], [7]]$

思路： 按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量， $p a t h$ 用来存放符合条件单一结果， $res u lt$ 用来存放符合条件结果的集合。回溯函数里一定有一个参数记录当前 $p a t h$ 里面值的和 $n o w s u m$ ；还需要一个参数为 $in t$ 型变量 $s t a r t I n d e x$ 。
所以整体代码如下：

List<List<Integer>> result=new ArrayList<>();
LinkedList<Integer> path=new LinkedList<>();
void backtracking(int target, int start, int nowsum, int[] candidates)

2.回溯函数终止条件
回溯出口，如果 $t a r g e t$ 里面的数量等于 $n o w s u m$ ，说明其到达叶子节点则将其加入到 $res u lt$ ，否则直接返回 $re t u r n$
代码如下：

if (nowsum > target)
            return;
        if (target == nowsum) {
            result.add(new ArrayList<>(path));
            return;
        }

3.回溯搜索的遍历过程
$f or$ 循环每次从 $s t a r t I n d e x$ 开始遍历，然后用 $p a t h$ 保存取到的节点i搜索的过程如下图：

实现代码如下：

for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            nowsum += candidates[i];
            backtracking(target, i, nowsum, candidates);// 不用i+1了，表示可以重复读取当前的数
            nowsum -= candidates[i];
            path.removeLast();
        }

完整的代码如下：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        result.clear();
        path.clear();
        backtracking(target, 0, 0, candidates);
        return result;
    }

    private void backtracking(int target, int start, int nowsum, int[] candidates) {
        if (nowsum > target)
            return;
        if (target == nowsum) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            nowsum += candidates[i];
            backtracking(target, i, nowsum, candidates);// 不用i+1了，表示可以重复读取当前的数
            nowsum -= candidates[i];
            path.removeLast();
        }
    }
}

Topic2组合总和||

题目：

给定一个候选人编号的集合 $c an d i d a t es$ 和一个目标数 $t a r g e t$ ，找出 $c an d i d a t es$ 中所有可以使数字和为 $t a r g e t$ 的组合。 $c an d i d a t es$ 中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。

输入： $c an d i d a t es = [10, 1, 2, 7, 6, 1, 5], t a r g e t = 8$
输出： $[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]$

思路： 按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量， $p a t h$ 用来存放符合条件单一结果， $res u lt$ 用来存放符合条件结果的集合。回溯函数里一定有一个参数记录当前 $p a t h$ 里面值的和 $n o w s u m$ ；还需要一个参数为 $in t$ 型变量 $s t a r t I n d e x$ ，还有一个用于记录是否被使用过的数组 $u se d$ 。
所以整体代码如下：

List<List<Integer>> result=new ArrayList<>();
LinkedList<Integer> path=new LinkedList<>();
void reback(int[] candidates,int target,int nowsum,int startindex)
boolean[] used;//记录元素是否被用过

2.回溯函数终止条件
回溯出口，如果索引值 $s t a r t in d e x$ 里面的数量等于 $d i g i t s . l e n g t h ()$ ，说明其到达叶子节点，则将 $t e m p$ 其加入到 $l i s t$ ，否则直接返回 $re t u r n$
代码如下：

if(target<nowsum)return;
        if(target==nowsum){
            result.add(new ArrayList<>(path));
        }

3.回溯搜索的遍历过程
首先将原始数据进行排序，进行排序后相同的数字就会相邻。如果 $c an d i d a t es [i] == c an d i d a t es [i - 1] 并且 u se d [i - 1] == f a l se$ ，就说明：前一个树枝，使用了 $c an d i d a t es [i - 1]$ ，也就是说同一树层使用过 $c an d i d a t es [i - 1]$ 。此时 $f or$ 循环里就应该做 $co n t in u e$ 的操作。

实现代码如下：

for(int i=startindex;i<candidates.length;i++){
            if(i>startindex && candidates[i]==candidates[i-1])continue;
            nowsum+=candidates[i];
            path.add(candidates[i]);
            used[i]=true;
            reback(candidates,target,nowsum,i+1);
            nowsum-=candidates[i];
            path.removeLast();
            used[i]=false;
        }

完整的代码如下：

class Solution {
    List<List<Integer>> result=new ArrayList<>();//用于记录最后的结果
    List<Integer> path=new LinkedList<>();//用于记录临时结果
    boolean[] used;//记录元素是否被用过
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        result.clear();
        path.clear();
        used=new boolean[candidates.length];
        Arrays.fill(used, false);
        reback(candidates,target,0,0);
        return result;
    }
    private void reback(int[] candidates,int target,int nowsum,int startindex){
        if(target<nowsum)return;
        if(target==nowsum){
            result.add(new ArrayList<>(path));
        }
        for(int i=startindex;i<candidates.length;i++){
            if(i>startindex && candidates[i]==candidates[i-1])continue;
            nowsum+=candidates[i];
            path.add(candidates[i]);
            used[i]=true;
            reback(candidates,target,nowsum,i+1);
            nowsum-=candidates[i];
            path.removeLast();
            used[i]=false;
        }
    }
    private void reback1(int[] candidates,int target,int nowsum,int startindex){
        if(target<nowsum)return;
        if(target==nowsum){
            result.add(new ArrayList<>(path));
        }
        for(int i=startindex;i<candidates.length;i++){
            if(i>startindex && candidates[i]==candidates[i-1]){
                continue;
            }
            nowsum+=candidates[i];
            path.add(candidates[i]);
            reback(candidates,target,nowsum,i+1);
            nowsum-=candidates[i];
            path.removeLast();
        }
    }
}

时间复杂度: $O(n * 2^n)$
空间复杂度: $O (n)$

Topic3分割回文串

题目：

给你一个字符串 $s$ ，请你将 $s$ 分割成一些子串，使每个子串都是回文串。返回 $s$ 所有可能的分割方案。

输入： $s = " aab "$
输出： $[[" a ", " a ", " b "], [" aa ", " b "]]$

思路：

解决该问题需要解决下面几个问题：

切割问题可以抽象为组合问题
如何模拟那些切割线
切割问题中递归如何终止
在递归循环中如何截取子串

如何判断回文按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量， $p a t h$ 用来存放符合条件单一结果， $res u lt$ 用来存放符合条件结果的集合。回溯函数里一定有一个参数记录当前 $p a t h$ 里面值;还需要一个参数为 $in t$ 型变量 $in d e x$ 。
所以整体代码如下：

List<List<String>> result = new ArrayList<>();// 存最后的结果
Deque<String> path = new LinkedList<>();// 存中间的结果
void reback(String s, int index)

2.回溯函数终止条件
回溯出口，从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

代码如下：

 if (index >= s.length()) {
            result.add(new ArrayList(path));
            return;
        }

3.回溯搜索的遍历过程
首先判断这个子串是不是回文，如果是回文，就加入在 $p a t h$ 中， $p a t h$ 用来记录切割过的回文子串。

实现代码如下：

for (int i = index; i < s.length(); i++) {
            if (isHuiwen(s, index, i)) {
                String str = s.substring(index, i + 1);
                path.addLast(str);
            } else {
                continue;
            }
            reback(s, i + 1);
            path.removeLast();
        }

完整的代码如下：

class Solution {
    List<List<String>> result = new ArrayList<>();// 存最后的结果
    Deque<String> path = new LinkedList<>();// 存中间的结果

    public List<List<String>> partition(String s) {
        reback(s, 0);
        return result;
    }

    private void reback(String s, int index) {
        if (index >= s.length()) {
            result.add(new ArrayList(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (isHuiwen(s, index, i)) {
                String str = s.substring(index, i + 1);
                path.addLast(str);
            } else {
                continue;
            }
            reback(s, i + 1);
            path.removeLast();
        }
        
    }
    private boolean isHuiwen(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;
    }
}