代码随想录 day 26

回溯

组合总和
题意：一个无重复元素的整数数组；一个目标整数target； 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ；并以列表形式返回。candidates 的同一个数字可以无限制重复被选取。
思路：因为同一个元素可以无限制重复地被选取。所以startidx 可以是相同的（重复选取）。
核心代码：

void backtracking(vector<int>& candidates, int sum_ , int startidx)
    {
        if(target_ == sum_)
        {
            // cnt ++ ;
            res.push_back(re) ; 
            return ; 
        }
        if(sum_> target_ ) // 并且减多了也要返回没有料到   。   
        {
            return ; 
        }
        // 剪枝一般在遍历剪
        //  如果 下一层相加的和 大于 target 就减掉 。
        // i是遍历树层的节点  i= 0 是第一个节点，i = 1 是第2个节点 。 i = 3 是第三个节点
        for(int i = startidx ; i< candidates.size()  && sum_ + candidates[i] <= target_ ; ++ i)
        {
            sum_ += candidates[i] ;
            re.push_back(candidates[i]) ; 
            backtracking(candidates , sum_ , i ) ; // 同一个数字可以被无限选取。 从i开始startidx 没有料到 ； 
            re.pop_back() ;  
            sum_ -= candidates[i] ; 
        }
    }

组合总和II
题意：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidate只用一次。
思路：是从candidates 中找到数使得和为target ； 同一层的元素相同的元素使用过的， 要把其给去重掉。所谓去重，其实就是使用过的元素不能重复选取。 所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为什么used[i-1] = false 是同一树层的呢，因为同一树层，used[i-1] = false 才能表示，当前取的candidate[i]是从candidate[i-1] 回溯而来的。 used[i-1] = true 是进入下一层递归的树 ；

单层递归的逻辑

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
    // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
    // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
    // 要对同一树层使用过的元素进行跳过
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue;
    }
    sum += candidates[i];
    path.push_back(candidates[i]);
    used[i] = true;
    backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}

分割回文串
题意：是给一个字符串s,将s分割成一些子串，使这些子串都是回文串。 返回 s 所有可能的分割方案。
思路：树的每个节点要做的就是切割子串。把子串收集好，切割完毕之后才做这次判断。 回溯三部曲：1.返回类型为void ， 参数因为下次递归要从startidx开始，所以需要传入startidx； 递归边界：切割线大于串的长度就是返回的时候。递归体 默写：for(int i = startidx; i < s.size() ; ++ i ) { re.push_back() ; // 切割的子串 ； backtracking(s , i+1) ; re.pop_back() ; }
核心代码

 void backtracking(string s  , int startidx )  
    {
        if(startidx>= s.size())
        {
            int flag = 0 ; 
            for(auto it : re)
            {
               if(!judge(it))
               {
                    flag =1; 
                    break  ;
               }
            }
            // cout<<endl; 
            if(flag == 0 )
            res.push_back(re) ; 
            return  ; 
        }
        for(int i = startidx ; i<s.size() ; ++ i )
        {
            
            // int delim = i+1 ;  // 左闭右开切割。 

            re.push_back(s.substr(startidx, i- startidx+1  )) ; // 要把分割的串加入到re 中，最后统一处理； 判断是否是回文串。 
            // pre = delim ;   
            backtracking(s , i + 1 ) ;  // i+1 
            re.pop_back() ; 
            // pre = i ; 
        }
    }