代码随想录算法训练营day26

题目：39. 组合总和、40.组合总和II、131.分割回文串

参考��接：代码随想录

39. 组合总和

思路：本题有点像以前做过的k数之和，前者使用的是双指针法，但本题没给定取的数的个数，故只能用回溯法。本题同一个数字可以重复取，但我们还是要设置开始位置，我们采用target递减的方法来判断总和。返回条件为target==0，for循环遍历第一个元素的选择，递归遍历后续元素的选择。当目前后续元素大于所需和的时候直接返回（剪枝），注意首先要对数组排序。时间复杂度O(n*2^n)。

class Solution {public:    vector ans;    vector path;    void backtracking(vector& candidates,int target,int begin){        if(target==0){            ans.push_back(path);            return;        }        for(int i=begin;i            if(target//剩下的所需和小于目前候选的元素，直接返回                return;            }            path.push_back(candidates[i]);            backtracking(candidates,target-candidates[i],i);//下一层递归依旧从i开始，因为可以重复            path.pop_back();        }    }    vector        sort(candidates.begin(),candidates.end());        backtracking(candidates,target,0);        return ans;    }};public:    vector        if(target==0){            ans.push_back(path);            return;        }        for(int i=begin;i            if(target//剪枝                return;            }            path.push_back(candidates[i]);            backtracking(candidates,target-candidates[i],i+1);            path.pop_back();        }    }    vector        sort(candidates.begin(),candidates.end());        backtracking(candidates,target,0);        return ans;    }};public:    vector        if(target==0){            ans.push_back(path);            return;        }        for(int i=begin;i            if(target//剪枝                return;            }            if(i0 && candidates[i]==candidates[i-1] && used[i-1]==0){                continue;//去重过程，树层相邻的相同则直接跳过            }            path.push_back(candidates[i]);            used[i]=1;            backtracking(candidates,target-candidates[i],i+1,used);            path.pop_back();            used[i]=0;        }    }    vector        sort(candidates.begin(),candidates.end());        vectorpublic:    vector        if(target==0){            ans.push_back(path);            return;        }        for(int i=begin;i            if(target//剪枝                return;            }            if(ibegin && candidates[i]==candidates[i-1]){                continue;//去重过程，树层相邻的相同则直接跳过            }            path.push_back(candidates[i]);            backtracking(candidates,target-candidates[i],i+1);            path.pop_back();        }    }    vector        sort(candidates.begin(),candidates.end());        backtracking(candidates,target,0);        return ans;    }};public:    bool isPalindrome(const string s,int begin,int end){//左闭右开，判断begin到end是不是回文串        while(begin            if(s[begin]!=s[end-1]){                return false;            }            begin++;            end--;        }        return true;    }    vector//begin为开始位置，end为切割位置        if(ends.size()){//切割结束,            ans.push_back(path);            return;        }        for(int i=end;i            if(!isPalindrome(s,begin,i)){//第一次切割就不是回文串，直接下一种切割                continue;            }            //第一种切割是回文串            path.push_back(string(s.begin()+begin,s.begin()+i));//加入结果            backtracking(s,i,i+1);            path.pop_back();        }    }    vector        backtracking(s,0,1);        return ans;    }};