刷题笔记Day23回溯算法part02

刷题笔记Day23：回溯算法part02

题目：组合总和

39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：

1. 输入：candidates = [2,3,6,7], target = 7
2. 输出：[[2,2,3],[7]]
3. 解释：
4. 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
5. 7 也是一个候选， 7 = 7 。
6. 仅有这两种组合。

复制代码

反思：在写本体的时候我还是按照Day22中的思路去写，发现一个问题就是无法实现代码中的去重逻辑，如果按照之前的逻辑写，每一次for循环都去遍历一遍整个candidates，这样写随让能找到所有的元素但是回碰到找到的元素包含[2,2,3],[2,3,2],[3,2,2]这三种情况，因此为了避免在这种现象的发生，需要进行去重操作，在此处使用的是入下图中的逻辑，在向前递归的过程中增加开始变量让for循环的起始位置在第一次进入递归的位置之后，如下图一样，当从3开始递归时候他在向下递归的过程中只能选择[3,6,7]这几个数字。

代码：

1. class Solution {
2. public:
3.     vector<int> nums;
4.     vector<vector<int>> result;
5.     void backtracking(vector<int>& candidates, int index, int target)
6.     {
7.         //终止条件
8.         int nums_sum = 0;
9.         for(int i = 0; i <nums.size();i++)
10.         {
11.             nums_sum += nums[i];
12.         }
13.         if(nums_sum >= target )
14.         {
15.             if(nums_sum == target)
16.             {
17.                 result.push_back(nums);
18.             }
19.             return;
20.         }
22.         //for循环处理横向逻辑
23.         for(int i = index;i<candidates.size();i++)
24.         {
25.             nums.push_back(candidates[i]);
26.             backtracking(candidates,i,target);
27.             nums.pop_back();
28.         }
29.         
30.         return;
31.     }
32.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
33.         backtracking(candidates,0,target);
34.         return result;
35.     }
36. };

复制代码

题目：分割回文串

131. 分割回文串 - 力扣（LeetCode）
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：

1. 输入: candidates = [10,1,2,7,6,1,5], target = 8,
2. 输出:
3. [
4. [1,1,6],
5. [1,2,5],
6. [1,7],
7. [2,6]
8. ]

复制代码

示例 2：

1. class Solution {
2. public:
3.     vector<int> nums;
4.     vector<vector<int>> result;
5.     void backtracking(vector<int>& candidates, int index, int target)
6.     {
7.         //终止条件
8.         int nums_sum = 0;
9.         for(int i = 0; i <nums.size();i++)
10.         {
11.             nums_sum += nums[i];
12.         }
13.         if(nums_sum >= target || nums.size() == candidates.size())
14.         {
15.             if(nums_sum == target)
16.             {
17.                 result.push_back(nums);
18.             }
19.             return;
20.         }
22.         //for循环处理横向逻辑
23.         for(int i = index;i<candidates.size();i++)
24.         {
25.             if(i>index && candidates[i] == candidates[i-1])
26.             {
27.                 continue;
28.             }
29.             nums.push_back(candidates[i]);
30.             backtracking(candidates,i+1,target);
31.             nums.pop_back();
32.         }
33.         
34.         return;
35.     }
36.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
37.         sort(candidates.begin(),candidates.end());
38.         backtracking(candidates,0,target);
39.         return result;
40.     }
41. };

复制代码

思路：通过递归的方式遍历所有可能子串，在遍历的过程中子串的过程中筛选是否为回文串，遍历的逻辑如下：

代码：(一定要注意切割子串的起始位置和终止位置)
[code]class Solution {public:    vector one;    vector result;        void backtracking(string s , int start_index)    {        //判断在递归之前，因此此处仅作为结果的收集        if(start_index == s.size())        {            result.push_back(one);            return;        }        for(int i = start_index;i