Moc obliczeniowa 2^n – skrypt sprawdzający wszystkie możliwe sumy

Mam dwie tabele a[n] i b[n] i chcę rozważać wszystkie zerowe sumy x[0]+x[1]+...+x[n-1]=S, takie, że x[i]∈{a[i];b[i]}. Jak mógłby wyglądać skrypt sprawdzający wszystkie możliwe sumy S?

Jestem początkujący, więc proszę mnie nie skreślać. Liczę na waszą pomoc :)

Co znaczy: x[i]∈{a[i];b[i]}? Należy do przedziału, jest jednym albo drugim? Sumy zerowe, czyli sumy równe zero?

Rozumiem, że rozwiązanie w czasie O(2^n) Ciebie zadowala?

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;
}