#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <stdexcept>
/*
Two Sum — Return UNIQUE Value Pairs
-----------------------------------
Goal:
Given a list of integers and a target value, return all UNIQUE value
pairs (a, b) such that a + b == target.
Definition of "unique":
- Pairs are unique by VALUE, not by index.
- (1, 3) is the same as (3, 1); store sorted pairs.
- If multiple index combinations produce the same value pair,
return it only once.
Algorithm:
- Use a hash set to track seen values.
- Use another hash set to store unique pairs (encoded as strings or
structs) to avoid duplicates.
- For each number:
complement = target - number
If complement is in seen:
store sorted pair (min, max)
Insert number into seen.
Why this approach:
- Efficient: single pass, O(n) average-case.
- Avoids duplicates naturally.
- No sorting of the entire array required.
Complexity:
- Time: O(n) average-case.
- Space: O(n) for sets.
Pitfalls:
- Many duplicates: ensure pair uniqueness logic is correct.
- Large values: avoid overflow when computing complement.
- No solution: return empty vector.
Security Notes:
- No raw pointers; no manual memory management.
- No undefined behavior; bounds checked.
Architecture Notes:
- Core logic isolated in a function (twoSumUniquePairs).
- Main demonstrates multiple test scenarios.
- Clear separation of concerns: computation vs. I/O.
Test Edge Cases:
- Empty vector
- Single element
- No valid pair
- Multiple duplicates
- Negative numbers
- Large values
*/
struct PairHash {
// Hash for pair<int,int> so it can be stored in unordered_set
std::size_t operator()(const std::pair<int,int>& p) const noexcept {
return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
}
};
std::vector<std::pair<int,int>> twoSumUniquePairs(const std::vector<int>& nums, int target) {
std::unordered_set<int> seen; // values we've encountered
std::unordered_set<std::pair<int,int>, PairHash> uniquePairs;
for (int value : nums) {
int complement = target - value;
if (seen.count(complement)) {
// Sort pair to ensure uniqueness (a,b) == (b,a)
int a = std::min(value, complement);
int b = std::max(value, complement);
uniquePairs.emplace(a, b);
}
seen.insert(value);
}
// Convert set to vector
return { uniquePairs.begin(), uniquePairs.end() };
}
void printPairs(const std::vector<std::pair<int,int>>& pairs) {
if (pairs.empty()) {
std::cout << "No unique pairs found.\n";
return;
}
for (const auto& p : pairs) {
std::cout << "(" << p.first << ", " << p.second << ")\n";
}
}
int main() {
// Test 1: Basic example
{
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
std::cout << "Test 1:\n";
auto pairs = twoSumUniquePairs(nums, target);
printPairs(pairs);
std::cout << "\n";
}
// Test 2: Multiple duplicates producing same value pair
{
std::vector<int> nums = {1, 3, 1, 3, 1, 3};
int target = 4;
std::cout << "Test 2:\n";
auto pairs = twoSumUniquePairs(nums, target);
printPairs(pairs);
std::cout << "\n";
}
// Test 3: Negative numbers
{
std::vector<int> nums = {-1, -2, -3, -4, -5};
int target = -6;
std::cout << "Test 3:\n";
auto pairs = twoSumUniquePairs(nums, target);
printPairs(pairs);
std::cout << "\n";
}
// Test 4: No valid pairs
{
std::vector<int> nums = {10, 20, 30};
int target = 100;
std::cout << "Test 4:\n";
auto pairs = twoSumUniquePairs(nums, target);
printPairs(pairs);
std::cout << "\n";
}
// Test 5: Mixed values with multiple unique pairs
{
std::vector<int> nums = {5, 5, 5, 5, 2, 8, 3, 7};
int target = 10;
std::cout << "Test 5:\n";
auto pairs = twoSumUniquePairs(nums, target);
printPairs(pairs);
std::cout << "\n";
}
}
/*
run:
Test 1:
(2, 7)
Test 2:
(1, 3)
Test 3:
(-5, -1)
(-4, -2)
Test 4:
No unique pairs found.
Test 5:
(3, 7)
(2, 8)
(5, 5)
*/
