Coin Change
Boundary:
- There may be no possible change, so in this scenario, should check when existing amount + coin exceed amount.
- Target amount is 1.
- Single coin value greater than target amount.
Palindrome Partitioning
class Solution {
public:
void addstring (vector<vector<string>> &res,int k, int m){
for(int i=m;i<res[k].size()-1;i++){
if(i>0&&res[k][i-1]==res[k][i+1]){
vector<string> next;
for(int j=0;j<i-1;j++) next.push_back(res[k][j]);
next.push_back(res[k][i-1]+res[k][i]+res[k][i+1]);
for(int j=i+2;j<res[k].size();j++) next.push_back(res[k][j]);
res.push_back(next);
addstring(res,res.size()-1, i-1);
}
if(res[k][i].length()==1&&res[k][i]==res[k][i+1]){
vector<string> next;
for(int j=0;j<i;j++) next.push_back(res[k][j]);
next.push_back(res[k][i]+res[k][i+1]);
for(int j=i+2;j<res[k].size();j++) next.push_back(res[k][j]);
res.push_back(next);
addstring(res,res.size()-1,i);
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> cur;
for(int i=0;i<s.length();i++){
cur.push_back(string(1,s[i]));
}
res.push_back(cur);
if(s.length()<=1) return res;
addstring(res, 0,0);
return res;
}
};
Backtracking 的想法沒問題阴幌，但是addstring之后如果又從頭開始尋找集峦，可能會(huì)產(chǎn)生 1位置的add之后，再次搜尋腹鹉，搜尋到2位置社露， 12都有新的string青柄， 然后在第一輪略過1搜尋到2位置毅整，進(jìn)入下一輪迭代又搜尋到1位置阵漏，造成重復(fù)驻民。 Backtracking很重要的一點(diǎn)是記錄現(xiàn)在搜尋的位置，之后的迭代不用再次搜尋履怯。
