Given a set S, find all the maximal subsets whose sum <= k

Question

This is a Facebook interview question I came across at an online portal.

Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Hints:

• Output doesn't contain any set which is a subset of other.
• If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted.
• Lexicographic ordering may be used to solve it.

Any ideas how could this be solved?

Answer 1

I have some idea - you need a tree.

If you have given input of {1, 2, 3, 4, 5}, and you're searching for maximal subsets - you should build a tree starting from the biggest numbers, and allways expand while sum <= k (so don't stop on 4-2, but go down to 1 to get 4-2-1).

So, nodes starting from 5 would be: 5-1 / 5-2 - only those 2 have sum <= 7

starting from 4: 4-3 / 4-2-1 / 4-1 (subset of previous)

starting from 3: 3-2-1 / 3-1 (subset of previous)

starting from 2: 2-1 (subset of 3-2-1)

starting from 1: 1 (subset of 2-1)

Then you can sort valid outputs and get {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Answer 2

I know it's late to answer, but I think I've found a simple solution for this problem. We enumerate subsets of S in lexicographical order using backtracking and check the sum of subset generated so far.

When the sum exceeds k, the interesting part comes: we need to check if the generated subset is a proper subset of previously reported items.

One solution is to keep all the reported subsets and check for inclusion, but it's wasteful.

Instead, we calculate the difference between the k and the sum. If there is an element e in S such that e not in subset and e <= (k - sum), then the set we generated is a proper subset of a previously reported subset, and we can safely skip it.

Here is the complete working program in plain old C++, demonstrating the idea:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

typedef std::set<int> Set;
typedef std::vector<int> SubSet;

bool seen_before(const Set &universe, const SubSet &subset, int diff) {
    Set::const_iterator i = std::mismatch(universe.begin(), universe.end(),
                                          subset.begin()).first;
    return i != universe.end() && *i <= diff;
}

void process(const SubSet &subset) {
    if (subset.empty()) {
        std::cout << "{}\n";
        return;
    }
    std::cout << "{" << subset.front();
    for (SubSet::const_iterator i = subset.begin() + 1, e = subset.end();
         i != e; ++i) {
        std::cout << ", " << *i;
    }
    std::cout << "}\n";
}

void generate_max_subsets_rec(const Set &universe, SubSet &subset,
                              long sum, long k) {
    Set::const_iterator i = subset.empty()
        ? universe.begin()
        : universe.upper_bound(subset.back()),
        e = universe.end();
    if (i == e) {
        if (!seen_before(universe, subset, k - sum))
            process(subset);
        return;
    }
    for (; i != e; ++i) {
        long new_sum = sum + *i;
        if (new_sum > k) {
            if (!seen_before(universe, subset, int(k - sum)))
                process(subset);
            return;
        } else {
            subset.push_back(*i);
            if (new_sum == k)
                process(subset);
            else
                generate_max_subsets_rec(universe, subset, new_sum, k);
            subset.pop_back();
        }
    }
}

void generate_max_subsets(const Set &universe, long k) {
    SubSet subset;
    subset.reserve(universe.size());
    generate_max_subsets_rec(universe, subset, 0, k);
}

int main() {
    int items[] = {1, 2, 3, 4, 5};
    Set u(items, items + (sizeof items / sizeof items[0]));
    generate_max_subsets(u, 7);
    return 0;
}

The output is all maximum subsets in lexicographical order, one per line:

{1, 2, 3}
{1, 2, 4}
{1, 5}
{2, 5}
{3, 4}