代码随想录算法训练营第二十七天 |39.组合总和，40.组合总和II，131.分割回文串（已补充）

淩亂°似流年 2024-04-23 04:12 69阅读 0赞

### 39.组合总和（已观看） ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以**无限制重复被选取**。

说明：

*  所有数字（包括 target）都是正整数。
 *  解集不能包含重复的组合。

示例 1：

*  输入：candidates = \[2,3,6,7\], target = 7,
 *  所求解集为： \[ \[7\], \[2,2,3\] \]

示例 2：

*  输入：candidates = \[2,3,5\], target = 8,
 *  所求解集为： \[ \[2,2,2,2\], \[2,3,3\], \[3,5\] \]

4、视频链接：

[带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！\_哔哩哔哩\_bilibili][-_leetcode_39._ _bilibili]

class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(candidates); // 先进行排序
            backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
            return res;
        }
    
        public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
            // 找到了数字和为 target 的组合
            if (sum == target) {
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = idx; i < candidates.length; i++) {
                // 如果 sum + candidates[i] > target 就终止遍历
                if (sum + candidates[i] > target) break;
                path.add(candidates[i]);
                // 最后一个参数是i而不是i+1，是为了允许重复选择相同的数字
                backtracking(res, path, candidates, target, sum + candidates[i], i);
                path.removeLast(); // 回溯，移除路径 path 最后一个元素
            }
        }
    }

### 40.组合总和II（已观看） ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中**只能使用一次**。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

*  示例 1:
 *  输入: candidates = \[10,1,2,7,6,1,5\], target = 8,
 *  所求解集为:

[
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

*  示例 2:
 *  输入: candidates = \[2,5,2,1,2\], target = 5,
 *  所求解集为:

[
      [1,2,2],
      [5]
    ]

4、视频链接：

[回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II\_哔哩哔哩\_bilibili][LeetCode_40._II_bilibili]

class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(candidates);
            breakCrumb(res, new ArrayList<>(), candidates, target, 0, 0);
            return res;
        }
    
        private void breakCrumb(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int sum,
                                int start) {
            if (sum == target) {
                res.add(new ArrayList<>(list));
                return;
            }
            for (int i = start; i < candidates.length; i++) {
                // 如果 sum + candidates[i] > target 就终止遍历
                if (sum + candidates[i] > target) {
                    return;
                }
                // 去除重复元素
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                list.add(candidates[i]);
                // 最后一个参数是i而不是i+1，是为了允许重复选择相同的数字
                breakCrumb(res, list, candidates, target, sum + candidates[i], i + 1);
                list.removeLast();
            }
        }
    }

class Solution {
      List<List<Integer>> res = new ArrayList<>();
      LinkedList<Integer> path = new LinkedList<>();
      int sum = 0;
      
      public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort( candidates );
        backTracking( candidates, target, 0 );
        return res;
      }
      
      private void backTracking( int[] candidates, int target, int start ) {
        if ( sum == target ) {
          res.add( new ArrayList<>( path ) );
          return;
        }
        for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
          //正确剔除重复解的办法
          //跳过同一树层使用过的元素
          if ( i > start && candidates[i] == candidates[i - 1] ) {
            continue;
          }
    
          sum += candidates[i];
          path.add( candidates[i] );
          // i+1 代表当前组内元素只选取一次
          backTracking( candidates, target, i + 1 );
    
          int temp = path.getLast();
          sum -= temp;
          path.removeLast();
        }
      }
    }

### 131.分割回文串（已观看） ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: "aab" 输出: \[ \["aa","b"\], \["a","a","b"\] \]

4、视频链接：

[带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！\_哔哩哔哩\_bilibili][-_131._ _bilibili]

class Solution {
        List<List<String>> lists = new ArrayList<>();
        Deque<String> deque = new LinkedList<>();
    
        public List<List<String>> partition(String s) {
            backTracking(s, 0);
            return lists;
        }
    
        private void backTracking(String s, int startIndex) {
            // 如果起始位置大于s的大小，说明找到了一组分割方案
            if (startIndex >= s.length()) {
                lists.add(new ArrayList(deque));
                return;
            }
            for (int i = startIndex; i < s.length(); i++) {
                // 如果是回文子串，则记录
                if (isPalindrome(s, startIndex, i)) {
                    String str = s.substring(startIndex, i + 1);
                    deque.addLast(str);
                } else {
                    continue;
                }
                // 起始位置后移，保证不重复
                backTracking(s, i + 1);
                deque.removeLast();
            }
        }
    
        // 判断是否是回文串
        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;
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/combination-sum/
[Link 1]: https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[-_leetcode_39._ _bilibili]: https://www.bilibili.com/video/BV1KT4y1M7HJ
[LeetCode_ - 1]: https://leetcode.cn/problems/combination-sum-ii/
[Link 2]: https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_40._II_bilibili]: https://www.bilibili.com/video/BV12V4y1V73A
[LeetCode_ - 2]: https://leetcode.cn/problems/palindrome-partitioning/
[Link 3]: https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[-_131._ _bilibili]: https://www.bilibili.com/video/BV1c54y1e7k6