给定一组S，发现所有的最大的子集，其总和＆LT; = K [英] Given a set S, find all the maximal subsets whose sum <= k

问题描述

这是我碰到的一个在线门户网站Facebook的面试问题。

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

给定一组S，发现所有的最大的子集，其总和＆LT; = K。例如，若S = {1，2，3，4，5}和k = 7 输出是：{1，2，3} {1，2，4} {1,5} {2,5} {3,4}

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}

提示：

• 输出不包含任何集合是另一个的子集
• 如果X = {1，2，3}是一个溶液的X，则所有的子集{1} {2} {3} {1,2} {1,3} {2,3}被省略
• 词典式排序可以用来解决这个问题。

任何想法怎么会这样解决？

Any ideas how could this be solved?

推荐答案

我有一些想法 - 你需要的是一棵

I have some idea - you need a tree.

如果你给输入 {1，2，3，4，5} ，而你正在寻找最大的子集 - 你应该建立从开始的树形结构最大号码和传真展开，而总之＆LT; = K （所以不要停在4-2，但再往1获得4-2-1）

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).

所以，节点从5日起将是： 5-1 / 5-2 - 只有2有一笔＆LT; = 7

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

从4日开始： 4-3 / 4-2-1 / 4-1（的previous子集）

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

这3起： 3-2-1 / 3-1（的previous子集）

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

2起：2-1（3-2-1子集）

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

从1开始：1（2-1集）

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

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

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

这篇关于给定一组S，发现所有的最大的子集，其总和＆LT; = K的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！