Print All Combinations of a Number as a Sum of Candidate Numbers | LeetCode
http://yucoding.blogspot.com/2012/12/leetcode-question-16-combination-sum.html
DFS is enough to handle it.
The idea is to scan from the first to the last element from the ordered array. check every possible combination of these numbers(multiple times for a single element).
the end condition of the dfs function is
1. the target ==0 , print list, return
2. the target < 0 return
3. start position >= array size return
otherwise, from for each element in the array, dfs(start, target-element value);
details see the source code:
Read full article from Print All Combinations of a Number as a Sum of Candidate Numbers | LeetCode
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.
Here order is not important, so don’t print the duplicated combination.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set
A solution set is:
We may also assume that the candidate set does not contain duplicate numbers, as this will be redundant. We assume all numbers will be positive integers2,3,6,7 and target 7, A solution set is:
[7] [2, 2, 3] http://yucoding.blogspot.com/2012/12/leetcode-question-16-combination-sum.html
DFS is enough to handle it.
The idea is to scan from the first to the last element from the ordered array. check every possible combination of these numbers(multiple times for a single element).
the end condition of the dfs function is
1. the target ==0 , print list, return
2. the target < 0 return
3. start position >= array size return
otherwise, from for each element in the array, dfs(start, target-element value);
details see the source code:
void dfs(vector<int> &candidates, int target, vector<vector<int> > &res, vector<int> &r, int i){ if (target<0){ return; }else{ if (target==0){ res.push_back(r); }else{ while (i<candidates.size() && target-candidates[i]>=0){ r.push_back(candidates[i]); dfs(candidates,target-candidates[i],res,r,i); i++; r.pop_back(); } } } } vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > res; if (candidates.size()==0){return res;} sort(candidates.begin(),candidates.end()); vector<int> r; dfs(candidates,target,res,r,0); return res; }
void printSum(int candidates[], int index[], int n) {
for (int i = 1; i <= n; i++)
cout << candidates[index[i]] << ((i == n) ? "" : "+");
cout << endl;
}
void solve(int target, int sum, int candidates[], int sz, int index[], int n) {
if (sum > target)
return;
if (sum == target)
printSum(candidates, index, n);
for (int i = index[n]; i < sz; i++) {
index[n+1] = i;
solve(target, sum + candidates[i], candidates, sz, index, n+1);
}
}
void solve(int target, int candidates[], int sz) {
int index[10000];
index[0] = 0;
solve(target, 0, candidates, sz, index, 0);
}
Read full article from Print All Combinations of a Number as a Sum of Candidate Numbers | LeetCode
