dynamic dynamic programming for subset sum problem

ddp_ssp.cpp

#include <iostream>
#include <algorithm>

#include <cassert>

struct pair
{
    int term;
    int sum;
    pair operator + (int x)
    {
        return {x, sum + x};
    }
    bool operator < (const pair & p) const
    {
        return sum < p.sum;
    }
    explicit operator bool () const
    {
        return term != 0;
    }
    bool operator == (const pair & p) const
    {
        return sum == p.sum;
    }
};

pair ddp[2][1000];
auto src = ddp[0];
auto dst = ddp[1];

inline
auto add(int x)
{
    assert(x != 0);
    auto s = src;
    auto cur = s;
    auto d = dst;
    do {
        auto next = *s + x;
        while (next < *cur) {
            *d++ = *cur++;
        }
#if 0
        if (*cur == next) {
            ++cur;
        }
        *d++ = std::move(next);
#else
        if (*cur == next) {
            *d++ = *cur++;
        } else {
            *d++ = std::move(next);
        }
#endif
    } while (*s++);
    while ((*d++ = *cur++));
    std::swap(src, dst);
    return (d - src);
}

int main()
{
    int v[] = {1, 2, 4, 8, 16, 32, 64};
    src[0] = {};
    for (int x : v) {
        add(x);
    }
    do {
        std::cout << src->sum << ' ';
    } while (*src++);
    std::cout << std::endl;
}