Jeśli dobrze rozumiem, to suma zawsze zawiera n elementów. Każdy i-ty element sumy musi być równy a[i]
lub b[i]
.
Czyli licząc sumę, mamy możliwość wyboru z którego ciągu wybieramy liczbę.
Czyli brutal force wygląda tak:
template <typename F, typename T>
void iterateOverAlternativeSumsOf(const T& a, const T& b, F f)
{
assert(std::size(a) == std::size(b));
const auto n = std::size(a);
auto itemsToCheck = 1ul << n;
for (auto i = 0ul; i < itemsToCheck; ++i) {
decltype(a[i]) sum = {};
for (auto j = 0ul; j < n; ++i) {
sum += ((i & (1ul << j)) != 0) ? a[i] : b[i];
}
F(sum, i);
}
}
template <typename T>
std::vector<unsigned long> findZeroAlterSum(const T& a, const T& b)
{
std::vector<unsigned long> result;
iterateOverAlternativeSumsOf(a, b,
[&result](auto sum, auto i) {
if (sum == 0)
result.push_back(i);
});
return result;
}