代码随想录第20天|

1. class Solution {
2. public:
3.     vector<vector<int>> res;
4.     vector<int> path;
5.     int sum=0;
6.     void backtracking(vector<int>& candidates, int target,int startIndex){
7.         if(sum>target)
8.            return;
9.         if(sum==target){
10.             res.push_back(path);
11.             return;
12.         }
13.         for(int i=startIndex;i<candidates.size();i++){
14.             sum+=candidates[i];
15.             path.push_back(candidates[i]);
16.             backtracking(candidates,target,i);
17.             sum-=candidates[i];
18.             path.pop_back();
19.         }
20.     }
21.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
22.            backtracking(candidates,target,0);
23.            return res;
24.     }
25. };

复制代码

首先我们要明确集合的概念  不论顺序 只要元素不一样就是组合 所以我们从小向大下标遍历 避免出现重复组合 这时候因为元素可以无限利用 每次下标不消加一

1. class Solution {
2. public:
3.     int sum=0;
4.     vector<vector<int>> res;
5.     vector<int> path;
6.     void backtracking(vector<int>& candidates, int target,int startIndex,vector<bool>& used){
7.         if(sum>target)
8.            return;
9.         if(sum==target){
10.             res.push_back(path);
11.             return;
12.         }
13.         for(int i=startIndex;i<candidates.size();i++){
14.             //如何判断当前结点相同数值之前是否已经被遍历过
15.             if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)
16.                continue;
17.             used[i]=true;
18.             sum+=candidates[i];
19.             path.push_back(candidates[i]);
20.             backtracking(candidates,target,i+1,used);
21.             used[i]=false;
22.             sum-=candidates[i];
23.             path.pop_back();
24.         }
25.     }
26.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
27.            vector<bool> used(candidates.size(),false);
28.            sort(candidates.begin(),candidates.end());//排序使得相同元素相邻 方便剪枝
29.            backtracking(candidates,target,0,used);
30.            return res;
31.     }
32. };

复制代码

上一题：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中全部可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
这一题：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中全部可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能利用 一次 。
我们可以看出和前一题不同在于candidates元素可能重复  candidate的元素在每个组合只能利用一次
如果没有重复元素 只要startIndex（i）+1就可以， 但如果有重复元素就阐明即使每次startIndex（i）+1  反面的重复元素 比如两个 1 1 2 3 要天生 6 可能会天生两个 123 123 如何避免这种情况就是要在重复元素出现的时候避免重复遍历 反面的1可以看作前面的1的真子集 全部情况都是包罗的
所以只要遍历第一个重复元素就行 ，所以每次看前一个元素是否相称而且有没有被遍历到
利用bool数组 留意一条路径可以前后元素可以相同 同一层不能相同 所以true代表递归 false代表回溯 得证

1. class Solution {
2. public:
3.     vector<vector<string>> res;
4.     vector<string> path;
5.     bool ishuiwen(string s){
6.         int i=0,j=s.size()-1;
7.         while(i<j){
8.             if(s[i]!=s[j])
9.                 return false;
10.             i++;
11.             j--;
12.         }
13.         return true;
14.     }
15.     void backtracking(string s,int startIndex){
16.         if(startIndex>=s.size()){
17.            res.push_back(path);
18.            return;
19.         }
20.         for(int i=startIndex;i<s.size();i++){
21.             //从startINdex分隔
22.             string str=s.substr(startIndex,i-startIndex+1);
23.             if(ishuiwen(str)){
24.                 path.push_back(str);
25.             }else{
26.                 continue;
27.             }
28.             backtracking(s,i+1);
29.             path.pop_back();
30.         }
31.     }
32.     vector<vector<string>> partition(string s) {
33.           backtracking(s,0);
34.           return res;
35.     }
36. };

复制代码

分隔回文串
首先遍历切割位置 利用substr切割字符串
递归直到start超范围阐明乐成找到一组 留意 不要先都递归在判断 判断过程相当于剪枝直接镌汰重复情况。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。