Title:
https://leetcode.com/problems/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.
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 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
思路：基本是DFS的思想。将数组排序之后，每次对当前的这个元素与target比较，看最多能塞进去几个当前的这个元素。
如果数组有相同元素，可以采用注释掉的语句进行去重，或者在递归函数中去重。不去重也不会影响结果。(去掉蓝色的也没有影响，不过蓝色的是为了去重)
注意结束条件： 一般都是index == size(),但这边应该是0 == target
for (int i = (target / candidates[idx]); i >= 0; i--) {
record.push_back(candidates[idx]);
}
用来计算最多压入几个当前元素。
for (int i = (target / candidates[idx]); i >= 0; i--) {
record.pop_back();
searchAns(ans, record, candidates, target - i * candidates[idx], idx + 1,candidates[idx]);
//record.pop_back();
}
弹出栈，再进入递归函数。注意，有可能这个元素就不要压入，所以是i >=0
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(candidates.begin(), candidates.end());
/*vector<int>::iterator pos = unique(candidates.begin(), candidates.end());
candidates.erase(pos, candidates.end());*/
vector<vector<int> > ans;
vector<int> record;
searchAns(ans, record, candidates, target, 0,-1);
return ans;
}
private:
void searchAns(vector<vector<int> > &ans, vector<int> &record, vector<int> &candidates, int target, int idx, int preValue) {
if (target == 0) {
ans.push_back(record);
return;
}
if ( idx == candidates.size() || candidates[idx] > target || preValue == candidates[idx]) {
return;
}
for (int i = (target / candidates[idx]); i >= 0; i--) {
record.push_back(candidates[idx]);
}
for (int i = (target / candidates[idx]); i >= 0; i--) {
record.pop_back();
searchAns(ans, record, candidates, target - i * candidates[idx], idx + 1,candidates[idx]);
//record.pop_back();
}
}
};
Title:
https://leetcode.com/problems/combination-sum-ii/
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the 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 10,1,2,7,6,1,5 and target 8,
A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6]
思路：DFS搜索。与Combination Sum中的不同，每次搜索的备选项是从当前index开始到数组结束的元素。不包括重复元素。
class Solution {
public:
vector<vector<int> > results;
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
if (num.empty() || num.size() == 0)
return results;
sort(num.begin(),num.end());
vector<int> result;
combine(num,0,target,result);
return results;
}
void combine(vector<int> &num,int startIndex, int target,vector<int> &result){
if (0 == target){
//cout<<"add"<<endl;
results.push_back(result);
return ;
}
if (0 > target)
return ;
for (int i = startIndex; i < num.size(); i++){
if (i > startIndex && num[i] == num[i-1])
continue;
result.push_back(num[i]);
combine(num,i+1,target-num[i],result);
result.pop_back();
}
}
};
Title:
https://leetcode.com/problems/combination-sum-iii/
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int> > results;
if ( k < || n < )
return results;
vector<int> result;
DFS(results,result,,k,n,);
return results;
}
void DFS(vector<vector<int> >& results, vector<int>& result, int index, int k, int target, int preVal){
if (index == k && target == ){
results.push_back(result);
return ;
}
if (index == k || target <= preVal)
return ;
for (int i = preVal+; i < ; i++){
result.push_back(i);
DFS(results,result,index+,k,target-i,i);
result.pop_back();
}
}
};