程序员人生 网站导航

Combination Sum II

栏目:php教程时间:2015-03-19 08:00:36

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] 

#include<iostream> #include<vector> #include<algorithm> #include<numeric> #include<set> using namespace std; void FindcombinationSum(vector<vector<int> >&ResultVector, vector<int> &candidates, vector<int> &Oneresult, int target, int num = 0) { if (accumulate(Oneresult.begin(), Oneresult.end(), 0) >= target) return; for (int i = num; i != candidates.size();++i) { if (candidates[i] == candidates[i - 1] && i>num)//保证不前1个重复数字必须被使用 continue; Oneresult.push_back(candidates[i]); int sum = accumulate(Oneresult.begin(), Oneresult.end(), 0); if (sum == target) ResultVector.push_back(Oneresult); FindcombinationSum(ResultVector, candidates, Oneresult, target, i + 1); Oneresult.pop_back(); } } vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > ResultVector; vector<int> Oneresult; sort(candidates.begin(), candidates.end()); FindcombinationSum(ResultVector, candidates, Oneresult, target); return ResultVector; }


 

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐