问由给定数字相加而形成的所有可能的数字

EN

S[0] = {0}
r = 1: S[1] = {0} union {0+1} = {0,1}
r = 2: S[2] = {0,1} union {0+2,1+2} = {0,1,2,3}
r = 4: S[3] = {0,1,2,3} union {0+4,1+4,2+4,3+4} = {0,1,2,3,4,5,6,7}

const std::vector<unsigned> l = {1,2,4};
const unsigned sum = std::accumulate(l.begin(), l.end());
typedef std::vector<unsigned> Sum; // one possibility for a single value
typedef std::vector<Sum> Sums; // all possibilities for a single value
// the element all[i] will provide all possible subsets where the sum is equal to 'i'
std::vector<Sums> all(sum + 2); // we know that sum + 1 is impossible
// initialize with single values
for (auto i: l)
{
    all[i].push_back(Vector(1, i));
}
unsigned i = 1; // ignore 0
// stop as soon as a value doesn't have any subset
while (!all[i].empty())
{
    ++i;
    for (unsigned j = 1; i/2 > j; ++j)
    {
        const unsigned k = i - j;
        // as i == j+k, create all the relevant combinations
        for (const auto &sj: all[j])
        {
            for (const auto &sk: all[k])
            {
                all[i].push_back(sj);
                all[i].back.insert(all[i].end(), sk.begin(), sk.end());
            }
        }
    }
    if (0 == (i % 2))
    {
        // create all the possible decompositions out of i/2
        for (auto left = all[i/2].begin(); all[i/2].end() != left; ++left)
        {
            for (auto right = left + 1; all[i/2].end() != right; ++ right)
            {
                all[i].push_back(*left);
                all[i].back.insert(all[i].end(), right->begin(), right->end());
            }
        }
    }
}