# C++ Iterative solution which avoids duplicates

• We solve this the same way we would solve the subset-sum problem.

The key observation for avoiding duplicates is that if we are processing the `k'th` instance of a number, then it can only extend solutions that have `(k-1) 1's` (for example). So when processing the 3rd instance of a number, we only extend solutions with 2 instances of that number. If we sort the numbers initially, we are guaranteed that if a solution has to include `(k-1)` instances of a number, then the suffix of the solution must have those numbers. This check can be done in `O(1)` time because we process the numbers sorted.

``````class Solution {
typedef vector<int> soln_t;
typedef vector<soln_t> solns_t;
vector<solns_t> combo;

int getNum(soln_t &soln, int i, int def) {
if (i < 0 || i >= soln.size()) return def;
return soln[i];
}

bool hasExactlyK(soln_t &soln, int n, int k) {
int idx = soln.size() - 1;
bool ret = soln.size() >= k && getNum(soln, idx-k, n+1) != n && getNum(soln, idx-k+1, n) == n;
return ret;
}

public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
std::sort(candidates.begin(), candidates.end());
combo.clear();
combo.resize(target+1);
combo[0] = solns_t(1);
// Stores how many instances of a number have been seen so far.
unordered_map<int, int> seen;

for (int n: candidates) {
int instances = seen[n]++;
for (int i = target - n; i >= 0; --i) {
for (auto x: combo[i]) {
if (hasExactlyK(x, n, instances)) {
x.push_back(n);
combo[i + n].push_back(x);
}
}
}
}
return combo[target];
}
};
``````

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