#include <iostream>
#include <set>
#include <vector>
std::vector<std::pair<int, int>> find_sums(const std::set<int>&s, int total)
{
if (s.empty()) {
return {};
}
auto b = s.begin();
auto e = s.end();
--e;
std::vector<std::pair<int, int>> res;
do {
auto sum = *b + *e;
if (sum == total) {
res.push_back({*b, *e});
++b;
} else if (sum < total) {
++b;
} else { // sum > total
if (e == s.begin()) {
break;
}
--e;
}
} while (b != e);
return res;
}
void print(const std::vector<std::pair<int, int>>& pairs)
{
for (const auto& p : pairs) {
std::cout << "{" << p.first << ", " << p.second << "} ";
}
std::cout << std::endl;
}
int main() {
print(find_sums({1, 3, 5, 7, 11, 20}, 10)); // {3, 7}
print(find_sums({1, 3, 5, 7, 11, 20}, 12)); // {1, 11}, {5, 7}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgoKc3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4gZmluZF9zdW1zKGNvbnN0IHN0ZDo6c2V0PGludD4mcywgaW50IHRvdGFsKQp7CglpZiAocy5lbXB0eSgpKSB7CgkJcmV0dXJuIHt9OwoJfQoJYXV0byBiID0gcy5iZWdpbigpOwoJYXV0byBlID0gcy5lbmQoKTsKCS0tZTsKCQoJc3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4gcmVzOwoJZG8gewoJCWF1dG8gc3VtID0gKmIgKyAqZTsKCQlpZiAoc3VtID09IHRvdGFsKSB7CgkJCXJlcy5wdXNoX2JhY2soeypiLCAqZX0pOwoJCQkrK2I7CgkJfSBlbHNlIGlmIChzdW0gPCB0b3RhbCkgewoJCQkrK2I7CgkJfSBlbHNlIHsgLy8gc3VtID4gdG90YWwKICAgICAgICAgICAgaWYgKGUgPT0gcy5iZWdpbigpKSB7CiAgICAgICAgICAgIAlicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICAtLWU7CgkJfQoJCQoJfSB3aGlsZSAoYiAhPSBlKTsKCQoJcmV0dXJuIHJlczsKfQoKdm9pZCBwcmludChjb25zdCBzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+PiYgcGFpcnMpCnsKCWZvciAoY29uc3QgYXV0byYgcCA6IHBhaXJzKSB7CgkJc3RkOjpjb3V0IDw8ICJ7IiA8PCBwLmZpcnN0IDw8ICIsICIgPDwgcC5zZWNvbmQgPDwgIn0gIjsKCX0KCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7Cn0KCgppbnQgbWFpbigpIHsKCXByaW50KGZpbmRfc3Vtcyh7MSwgMywgNSwgNywgMTEsIDIwfSwgMTApKTsgLy8gezMsIDd9CglwcmludChmaW5kX3N1bXMoezEsIDMsIDUsIDcsIDExLCAyMH0sIDEyKSk7IC8vIHsxLCAxMX0sIHs1LCA3fQp9