# Find Sum Pairs

``````/**
* Design an algorithm to find all pairs of integers within an array which
* sum to a specified value.
*/

/*
First some assumptions:
- I am going to assume that the same point cannot be used twice.
For example, if I have {1}, and my target is 2. Then I cannot have {1,1}
- Secondly, I am going to assume a number can used more than once. For
example: if I have {1,9,9,1} and my target is 10, then I can have both
{1, 9}, {9, 1}, {9, 1}, and {1, 9} (iterating left through right). So
if there is at least one number in the pair, then it is valid, and every
pair contains at least 1 unused element in the array.
- Duplicate pairs are allow, as so long as they follow the previous condition.

The Algorithm:
- Compile a hash table of the number and its frequency. Hash through with
target - data[i] to find a valid sum.
- If the data is the same as the difference, the frequency must be > 1
in order for the first assumption to make sense.
*/

vector<pair<int, int>> sum_pairs(vector<int> &data, int target)
{
vector<pair<int, int>> valid_pairs;
unordered_map<int, int> num_freq;

for (auto i : data) {
if (num_freq.find(i) == num_freq.end()) {
num_freq.insert({i, 1});
}
else num_freq[i]++;
}

for (int i = 0; i < data.size(); i++) {

int look_for = target - data[i];
auto found = num_freq.find(look_for);

if (found != num_freq.end()) { // found
if (look_for == data[i]
&& found->second > 1) { // duplicate
valid_pairs.push_back({data[i], look_for});
}
else if (look_for != data[i]){
valid_pairs.push_back({ data[i], look_for });
}
}
}

return valid_pairs;
}

/*
This next implementation is going constrain a few more assumptions:
- First assumption from above.
- No duplicate pairs

The Algorithm:
- Essentially the same as above, but we contain an additional container that
will contain the unique pairs. So before confirming an insertion for a valid
pair, we hash to the location of the pair and confirm whether it exists or not.

*/

struct pair_hash
{
inline size_t operator()(const pair<int, int> &p) const {
hash<int> int_hasher;
return int_hasher(p.first) ^ int_hasher(p.second);
}
};

vector<pair<int, int>> sum_pairs2(vector<int> &data, int target)
{
vector<pair<int, int>> valid_pairs;
unordered_map<int, int> num_freq;
unordered_set<pair<int, int>, pair_hash> unique_pairs;

for (auto i : data) {
if (num_freq.find(i) == num_freq.end()) {
num_freq.insert({ i, 1 });
}
else num_freq[i]++;
}

for (int i = 0; i < data.size(); i++) {

int look_for = target - data[i];
auto found = num_freq.find(look_for);
bool is_unique = unique_pairs.find({ data[i], look_for })
== unique_pairs.end();

if (found != num_freq.end() && is_unique){ // found and unique
if (look_for == data[i]
&& found->second > 1) { // duplicate
valid_pairs.push_back({ data[i], look_for });
unique_pairs.insert({ data[i], look_for });
}
else if (look_for != data[i]) {
valid_pairs.push_back({ data[i], look_for });
unique_pairs.insert({ data[i], look_for });
}
}
}

return valid_pairs;
}

void print_pairs(vector<pair<int, int>> &pairs)
{
for (auto i : pairs) {
cout << i.first << "," << i.second << endl;
}
}

int main()
{
vector<int> data = { 1,2,11,1,1,1,1,2,23,34,43,232,122,-20,30,2,3,4,7,9 };
vector<pair<int, int>> valid_pairs = sum_pairs(data, 10);
print_pairs(valid_pairs);
cout << endl;

vector<pair<int, int>> valid_pairs2 = sum_pairs2(data, 10);
print_pairs(valid_pairs2);

}``````

Last updated