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.
10,1,2,7,6,1,5
and target 8
, A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
A:
-----------Java-----------recursive--------------------
思路同上------------但是,在不用某个value 的时候,要直接退到后面,直到值不一样。public class Solution { public List<List<Integer>> combinationSum2(int[] A, int target) { Arrays.sort(A); return helper(A,0,target); } private List<List<Integer>> helper(int[] A, int start, int target){ List<List<Integer>> all = new LinkedList<List<Integer>>(); if(start>=A.length || target < A[start]) return all; if(target == A[start]){ List<Integer> list = new LinkedList<Integer>(); list.add(target); all.add(list); return all; } all = helper(A,start+1,target-A[start]); for(List<Integer> al : all ) al.add(0,A[start]); while(start+1<A.length && A[start+1] == A[start]) start++; all.addAll(helper(A,start+1,target)); return all; } }
-----------C++ -------iterative ------------
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& C, int target) {
std::sort(C.begin(), C.end());
vector<vector<int>> res, tmpRes={{}};
vector<int> sumList = {0};
for(int i =0;i<C.size(); i++)
{
int val = C[i], nVal = 1;
while( i+1 < C.size() && C[i+1] == val ) // count of current val
{
i++;
nVal++;
}
int curCount = tmpRes.size();
for(int j = 0; j< curCount; ++j)
{
auto B = tmpRes[j];
auto curSum = sumList[j];
for(int k = 0; k<nVal; k++)
{
B.push_back(val);
curSum += val;
if (curSum < target){ // add to next round
auto C = B; //must create a copy, as B can change next round
tmpRes.push_back(C);
sumList.push_back(curSum);
}else if(curSum == target){
res.push_back(B);
}
}
}
}
return res;
}
};
Learned:
No comments:
Post a Comment