39. 组合总和

思路：

变量：

全局变量：

vector<vector<int>> result; vector<int>path；int sum=0;

函数变量：

vector<int>&candidates,int target, int startIndex

终止条件：

sum==target时将path放进result;

单层逻辑：

for(int i=startIndex;i<candidates.size();i++)

sum+=;path.push();backtracking(candidates,target,i);path.pop();sum-=;

注意：本题可以重复选取元素，因此单层内的嵌套回溯i不需要i+1；

剪枝：

if(sum>target) return;

看视频后：

和视频思路相同。

40.组合总和II

思路：

按照上一题进星类似思路，可以取相同值，因此单层搜索中i；但是由于有重复元素，不知道如何进行去重

看视频后：

组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。树层去重的话，需要对数组排序！

因此涉及去重的操作为

1. sort排序数组

2.增加一个bool的数组记录取元素的情况，并用以下判断

 if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}

剪枝：sum>target

131.分割回文串

思路：

无。

看视频后：

1. 写一个判断回文子串的函数

2. backtracking

变量：

全局：result，path

函数变量：string s,int starti;

终止条件：

if(starti==s.size()) //starti为切割的线

单层循环：

for(int i=starti;i<s.size();i++)

        {

            if(rv(s,starti,i))//判断是否为回文子串

            {

                string str=s.substr(starti,i-starti+1);//记录子串，范围是starti-i，切割范围

                path.push_back(str);

            }

            else 

                continue;//不是子串就跳过

            backtracking(s,i+1);

            path.pop_back();

        }

切割其实是一种组合问题，重要的是切割线和切割范围。注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

本题难点：

切割问题可以抽象为组合问题

如何模拟那些切割线

切割问题中递归如何终止

在递归循环中如何截取子串

如何判断回文