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

this facebook interview question came across @ online portal.

given set s, find maximal subsets sum <= k. example, if s = {1, 2, 3, 4, 5} , k = 7 output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

hints:

• output doesn't contain set subset of other.
• if x = {1, 2, 3} 1 of solution subsets of x {1} {2} {3} {1, 2} {1, 3} {2, 3} omitted.
• lexicographic ordering may used solve it.

any ideas how solved?

i have idea - need tree.

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

so, nodes starting 5 be: 5-1 / 5-2 - 2 have sum <= 7

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

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

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

starting 1: 1 (subset of 2-1)

then can sort valid outputs , {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}