给定集合S,找到其总和<= k的所有最大子集

Question

这是我在在线门户网站上看到的Facebook面试问题.

给定集合S,找到其总和<= k的所有最大子集.例如,如果S = {1,2,3,4,5}且k = 7输出是:{1,2,3} {1,2,4} {1,5} {2,5} {3 ,4}

提示:

• 输出不包含任何其他的子集.
• 如果X = {1,2,3}是解之一,那么X的所有子集{1} {2} {3} {1,2} {1,3} {2,3}被省略.
• 可以使用词典排序来解决它.

任何想法如何解决？

Answer 1

我有一些想法 - 你需要一棵树.

如果你已经输入了{1, 2, 3, 4, 5},并且你正在搜索最大的子集 - 你应该从最大的数字开始构建一个树,并且总是扩展while sum <= k(所以不要停在4-2,但是下降到1得到4- 2-1).

因此,从5开始的节点将是:5-1 / 5-2 - 只有那些2的总和<= 7

从4:4-3 / 4-2-1 /4-1开始(之前的子集)

从3:3-2-1 /3-1开始(之前的子集)

从2:2-1开始(3-2-1的子集)

从1:1开始(2-1的子集)

然后你可以对有效输出进行排序并获得{1,2,3} {1,2,4} {1,5} {2,5} {3,4}