Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
http://www.lintcode.com/en/problem/combination-sum/
Discussion
有点想subsets问题，所以还是DFS的思路，只是每个number是可以无限制重复出现的，所以就dfs下一层的时候还是 当前的number，而不是下一个number。
- 思路1：刚开始还是常规的DFS思路，每次update一个sum，当sum==target就输出，这是就要注意了，
因为可以重复出现，只有
sum < target时才记录，sum > target时就要把最后一个pop出来，并且 不要再dfs下一层了。 - 思路2：用gap表示sum与target的差距，每次dfs时update gap，好写很多。。。
// Time: O(k * n^k), k is max length of combination
// Space: O(k)
Solution 1
class Solution {
public:
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// write your code here
vector<vector<int> > result;
int n=candidates.size();
if(n==0) return result;
vector<int> solution;
sort(candidates.begin(), candidates.end());
int sum = 0;
dfs(candidates, target, solution, sum, result,0);
return result;
}
private:
void dfs(vector<int> &candidates, int target, vector<int> &solution, int &sum,
vector<vector<int> > &result, int start) {
int n = candidates.size();
if (sum == target) {
result.push_back(solution);
return;
}
for (int i = start; i<n; i++) {
if (sum < target) {//sum小的时候才扩展记录
sum += candidates[i];
solution.push_back(candidates[i]);
}
if (sum > target) {//sum大的时候已经加过了，pop出来，break不要继续在这一层dfs了
sum -= solution.back();
solution.pop_back();
break;
}
dfs(candidates, target, solution, sum, result, i);//注意是i不是i+1，因为可以重复出现
sum -= solution.back();//撤销记录
solution.pop_back();
}
}
};
`
Solution 2
// Time: O(k * n^k), k is max length of combination
// Space: O(k)
class Solution {
public:
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// write your code here
vector<vector<int> > result;
int n = candidates.size();
if(n==0) return result;
vector<int> solution;
sort(candidates.begin(), candidates.end());
dfs(candidates, target, solution, 0, result);
return result;
}
private:
void dfs(vector<int> &candidates, int gap, vector<int> &solution, int start,
vector<vector<int> > &result) {
if(gap == 0) {
result.push_back(solution);
return;
}
int n = candidates.size();
for(int i=start; i<n; i++) {
if(gap < candidates[i]) {//剪枝
break;
}
solution.push_back(candidates[i]);
dfs(candidates, gap-candidates[i], solution, i, result);
solution.pop_back();
}
}
};
dfs(candidates, gap-candidates[i], solution, i, result);gap是传值，通过gap-candidates[i]来update每次call dfs的时候gap。如果改成引用传递，那么要在dfs之后复原gap。如下：gap -= tmp; solSet.push_back(tmp); dfsCombinationSum(candidates, gap, solutions, solSet, i); gap += tmp; //复原gap solSet.pop_back();
Solutoin 3
把DFS改成iteration。参考N-Queens问题改iteration的思路。把递归改成迭代，就需要用一些变量来记录函数执行时的状态。在迭代中，循环以保存递归函数状态的变量进行。
这个问题的递归函数状态的变量是什么呢？是vector<int> &solution。改成迭代的时候保存对应的candidates的index。
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// write your code here
vector<vector<int> > result;
if(candidates.empty()) return result;
vector<int> solSet;
sort(candidates.begin(), candidates.end());
//dfsCombinationSum(candidates, target, result, solSet, 0);
int sum = 0;
int n = candidates.size();
vector<int> indices;
//if(sum < target) {
// indices.push_back(0);
//}
bool backing = false;
int id = 0;
while(true) {
sum += candidates[id];
if (sum < target) {//还没达到target，保存id
indices.push_back(id);
}
else if (sum > target) {//太大了，sum复原，然后还要再把indices弹出一次。
sum -= candidates[id];
if (indices.size() > 0) {
sum -= candidates[indices.back()];
id = indices.back() + 1;
indices.pop_back();
}
else {
break;
}
}
else {//刚刚好，那就记录solution，然后indices弹出一次。每次弹出的时候都要更新id
indices.push_back(id);
//outputSolutions
vector<int> sol;
for (int i = 0; i< indices.size(); i++) {
sol.push_back(candidates[indices[i]]);
}
result.push_back(sol);
sum -= candidates[indices.back()];
id = indices.back() + 1;
indices.pop_back();
}
while (id >= n) {//这个很关键，保证id<n
if (indices.empty()) {
return result;
}
else {
sum -= candidates[indices.back()];
id = indices.back() + 1;
indices.pop_back();
}
}
}
return result;
}
起始上面那个indices vector明明就是当stack在用。。。
class Solution {
public:
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int> > result;
int n = candidates.size();
stack<int> idx;
vector<int> path;
int cur = 0;
int sum = 0;
sort(candidates.begin(), candidates.end());
while(true) {
if(sum + candidates[cur] < target) {//don't update cur
sum += candidates[cur];
idx.emplace(cur);
path.emplace_back(candidates[cur]);
} else if(sum + candidates[cur] > target) { //roll back
if(idx.empty()) break;
sum -= candidates[idx.top()];
cur = idx.top()+1;
idx.pop();
path.pop_back();
} else {
path.emplace_back(candidates[cur]);
//idx.emplace_back(cur);
result.emplace_back(path);
cur++;
//idx.pop_back();
path.pop_back();
}
while(cur >= n) {
if(idx.empty()) {
return result;
}
sum -= candidates[idx.top()];
cur = idx.top()+1;
idx.pop();
path.pop_back();
}
}
return result;
}
};