39/40 Combination Sum(I/II)
Total Accepted: 83289
Total Submissions: 274461
Difficulty: Medium
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
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
Hide Similar Problems
(M) Letter Combinations of a Phone Number (M) Combination Sum II (M) Combinations (M) Combination Sum III (M) Factor Combinations
分析:
本題は前の3つのブログのテーマとほぼ同じ意味ですが、ここの組み合わせは同じ数字でいいです.
本題連動:
216. Combination Sum III
77. Combinations
78/90 Subsets (I/II)
以前の誤った答えは、どんなに痛い悟りだろうか.
Total Accepted: 62935
Total Submissions: 231780
Difficulty: Medium
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
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
Hide Similar Problems
(M) Combination Sum
分析:
上のテーマと区別しないで、もう分析しません!
所要時間16 ms
他人の優秀なアルゴリズムを学ぶ:8 ms
注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50853069
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895
Total Submissions: 274461
Difficulty: Medium
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]
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
Hide Similar Problems
(M) Letter Combinations of a Phone Number (M) Combination Sum II (M) Combinations (M) Combination Sum III (M) Factor Combinations
分析:
本題は前の3つのブログのテーマとほぼ同じ意味ですが、ここの組み合わせは同じ数字でいいです.
本題連動:
class Solution {
public:
void dfs(vector<int>& nums, vector<int> &subres,int sum, int start, int target)// ,
{
if(sum == target)// ,
{
result.push_back(subres);
return;
}
for (int i = start; i < nsize; i++)
{
if(nums[i] > target || (sum+nums[i]) > target)// ,
return;
subres.push_back(nums[i]);
dfs(nums, subres,sum+nums[i],i,target);// , 。
subres.pop_back();//
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
nsize=candidates.size();
if ( nsize == 0)
return result;
sort(candidates.begin(),candidates.end()); // ,
vector<int> subres;
dfs(candidates, subres,0,0, target);
return result;
}
private:
vector<vector<int > > result;
int nsize;
};
以前の誤った答えは、どんなに痛い悟りだろうか.
class Solution {
public:
void dfs(vector<int>& nums, vector<int> &subres,int sum, int start, int target)// ,
{
if(sum == target)// ,
{
result.push_back(subres);
return;
}
if(sum > target)// ,
{
return;
}
for (int i = start; i < nsize; i++)
{
sum+=nums[i];// !!!
subres.push_back(nums[i]);
dfs(nums, subres,sum,i,target);
subres.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
nsize=candidates.size();
if ( nsize == 0)
return result;
sort(candidates.begin(),candidates.end()); // ,
vector<int> subres;
dfs(candidates, subres,0,0, target);
return result;
}
private:
vector<vector<int > > result;
int nsize;
};
Total Accepted: 62935
Total Submissions: 231780
Difficulty: Medium
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]
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
Hide Similar Problems
(M) Combination Sum
分析:
上のテーマと区別しないで、もう分析しません!
所要時間16 ms
class Solution {
public:
void dfs(vector<int>& nums, vector<int> &subres,int sum, int start, int target)// ,
{
if(sum == target)// ,
{
if(!isSameVec(subres))
result.push_back(subres);
return;
}
for (int i = start; i < nsize; i++)
{
if(nums[i]>target || (sum+nums[i]) > target)//
return;
subres.push_back(nums[i]);
dfs(nums, subres,sum+nums[i],i+1,target);// , 。 ( sum)
subres.pop_back();//
}
}
bool isSameVec(vector<int> &sub)
{
for(int i=0;i<result.size();i++)
{
if(result[i]==sub)
return true;
}
return false;
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
nsize=candidates.size();
if ( nsize == 0)
return result;
sort(candidates.begin(),candidates.end()); // ,
vector<int> subres;
dfs(candidates, subres,0,0, target);
return result;
}
private:
vector<vector<int > > result;
int nsize;
};
他人の優秀なアルゴリズムを学ぶ:8 ms
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target)
{
sort(num.begin(),num.end());
vector<int> subresult;
dfs( 0, target, subresult, num);
return result;
}
void dfs(const int order, const int target, vector<int>& subresult, const vector<int>& num)
{
if(target==0)
{
result.push_back(subresult);
return;
}
for(int i = order;i<num.size();i++) // iterative component
{
if(num[i]>target)
return;
if(i&&num[i]==num[i-1] && i>order)
continue; // check duplicate combination
subresult.push_back(num[i]),
dfs(i+1,target-num[i],subresult,num); // recursive componenet
subresult.pop_back();
}
}
private:
vector<vector<int > > result;
};
注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50853069
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895