# [C++] A concise iterative solution.

• It doesn't keep track of the combination sum, because we can alter the target number at any time. And it can handle the duplicates easily by comparing the adjacent numbers.

``````class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &num, int target) {
vector<int> numbers = num;
sort(numbers.begin(), numbers.end());

vector<vector<int>> result;
vector<int> indices;  // store the indices of the numbers of a combination in non-descending order
int i = 0;
while (i < numbers.size()) {
if (target == numbers[i]) {
vector<int> subset;
subset.reserve(indices.size() + 1);  // avoid memory reallocations
for (int j : indices) subset.push_back(numbers[j]);
subset.push_back(target);
result.push_back(move(subset));  // move instead of copy
}
// Note: numbers.back() is the maximum
if (target <= numbers[i] ||
(target > numbers[i] && i == numbers.size() - 1) ||
(target > numbers.back() * (numbers.size() - i))) {
if (indices.empty()) return result;
// pop the last added number and update the target number
i = indices.back() + 1;
target += numbers[i-1];
indices.pop_back();
// avoid duplicates
while (i >= numbers.size() || numbers[i-1] == numbers[i]) {
if (i >= numbers.size()) {
if (indices.empty()) return result;
i = indices.back() + 1;
target += numbers[i-1];
indices.pop_back();
} else {
i++;  // ignore the same numbers
}
}
} else {
target -= numbers[i];
indices.push_back(i);
i++;
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.