这是我在一个在线门户网站上遇到的Facebook面试问题。给定一个集合S，找到所有的最大子集合，其总和<= k
给定一个集合S，找出总和为< = k的所有最大子集。例如，如果S = {1,2,3,4,5}并且k = 7，则输出是：{1,2,3} {1,2,4} {1,5} {2,5} {1，2，3} 3，4}
提示：
任何想法如何解决这个问题？
我有一些想法 - 你需要一棵树。
如果你已经给定输入的{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（以前的子集）
starti纳克从2：2-1（3-2-1的子集）
从1开始：1（2-1子集）
然后就可以有效输出进行排序，并获得{1，2，3 } {1,2,4} {1,5} {2,5} {3,4}
你能为它提出一些算法吗？ – 2012-03-11 12:04:34
我们将包含子集（满足<= 7规则）的节点保存在堆栈或队列或阵列中，并消除重复项并打印阵列。 – Rahul 2013-02-14 06:55:23
这是一个powerset问题。最近我发现了关于算法的this website，它一直在描绘我的想象力：因此接下来是powerset/combination解决方案。您可以简单地复制，粘贴和运行该程序。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public static void maximalSubset
(int sum, int[] set, int choose,List<Integer[]> exclusion) {
if(1>choose) return;
int combinationSize = combinationSize(set.length,choose);
int index[]=new int[choose];
Integer subSet[] = new Integer[choose];
for(int i=0; i<choose;i++)
index[i]=i;
for(int i=0; i<combinationSize; i++) {
if(i!=0)
nextCombination(index,set.length);
for(int x=0; x<choose; x++)
subSet[x]=set[index[x]];
if(summation(sum,subSet) && !excluded(subSet,exclusion)) {
System.out.println(Arrays.toString(subSet));
exclusion.add(Arrays.copyOf(subSet,subSet.length));
}
}
maximalSubset(sum,set,choose-1,exclusion);
}//
private static int combinationSize(int n, int r) {
int den,limit;
if(r>n-r) {
den=n-r;
limit=r;
}else {
den=r;
limit=n-r;
}
long result=1;
for(int i=n; i>limit;i--)
result*=i;
for(int i=2; i<=den;i++)
result/=i;
return (int)result;
}//
private static void nextCombination(int[] A, int n) {
int c=A.length;
int i=c-1;
while(n-c+i==A[i])
i--;
A[i]++;
for(int j=i; j<c; j++)
A[j]=A[i]+j-i;
}//
private static boolean summation(int sum, Integer[] S) {
for(int i:S)
sum-=i;
return sum>=0;
}//
private static boolean excluded(Integer[] needle,List<Integer[]> haystack) {
for(Integer[] H: haystack) {
int count=0;
for(int h: H)
for(int n:needle)
if(h==n) {
count++;
break;//it's a set
}
if(count==needle.length)
return true;
}
return false;
}//
public static void main(String[] args) {
int[] S = {1, 2, 3, 4, 5};
int k = 7;
List<Integer[]> exclusion = new ArrayList<Integer[]>();
maximalSubset(k,S,S.length,exclusion);
}
}
@Raman Bhatia有没有理由不接受这个答案？乐意效劳。 – kasavbere 2012-03-23 23:27:13
该解决方案看起来非常复杂，难以理解，没有其他评论/解释 – HitOdessit 2015-01-17 15:09:22
我很抱歉在这么晚的碎裂。但是做这个怎么样？
1）从给定的阵列构建最小堆结构/设定
2）遍历从根的结构和保持在减去所访问节点的值。一旦你超过了所需的总和（curr_sum> k），输出这个路径，回溯到父节点并采取另一个路径（这可以递归地完成）。 3）如果回溯使您回到您开始的原始节点，则从root-> left节点递归实现整个算法。
4）现在执行与上述相同的两个步骤（2）和（3），但使用MAX-HEAP。
我新的算法和数据结构，而只是开始阅读简介交易算法，Cormen。这可能是一个错误的解决方案，但如果有人指出故障给我:)
我知道它的晚来回答我会很乐意，但我想我已经找到了这个问题的简单解决方案。我们使用回溯法列举按照字典顺序排列的S的子集，并检查到目前为止生成的子集的sum。
当sum超过k时，有趣的部分是：我们需要检查生成的subset是否是先前报告的项目的正确子集。
一个解决方案是保留所有报告的子集并检查包含，但这是浪费。
相反，我们计算k和sum之间的差异。如果在S这样e not in subset和e <= (k - sum)元素e，那么我们所产生的一组是先前报道的子集的真子集，我们可以跳过它。
这里是普通的老式C++的完整的工作程序，充分展示了主意：
#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;
}
输出是字典顺序所有最大的子集，每行一个：
{1, 2, 3}
{1, 2, 4}
{1, 5}
{2, 5}
{3, 4}
个老问题但仍然是一个有趣的。
下面是递归Java 8解决方案，采用“置换”方法。
优化清洁和更短的代码，而不是性能 - 例如排序和修剪将只需要发生一次。
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Ordering;
import java.util.*;
import java.util.stream.Collectors;
public class SubsetFinder {
public List<List<Integer>> findSubsets(List<Integer> input, int k) {
List<List<Integer>> listOfLists = new ArrayList<>();
List<Integer> copy = Ordering.natural().sortedCopy(input);
while (!copy.isEmpty()) {
int v = copy.remove(copy.size() - 1);
if (v == k || (copy.isEmpty() && v <= k)) {
// No need to look for subsets if the element itself == k, or
// if it's the last remaining element and <= k.
listOfLists.add(new ArrayList<>(Arrays.asList(v)));
} else if (v < k) {
findSubsets(copy, k - v).forEach(subList -> {
subList.add(v);
listOfLists.add(subList);
});
}
}
// Prune sets which are duplicates or subsets of other sets
return listOfLists.stream().filter(
candidate -> listOfLists.stream().noneMatch(
lol -> candidate != lol && lol.containsAll(candidate)
)
).collect(Collectors.toList());
}
}
为了测试它：
public static void main(String[] args) {
new SubsetFinder()
.findSubsets(ImmutableList.of(1, 2, 3, 4, 5), 7)
.forEach(System.out::println);
}
算法如下：
工作液低于：
public class Test {
/**
* Assuming alphabet[] is already sorted in increasing order
*/
public static void printMaximalSubSetsToSum(int[] alphabet, int sum) {
if (alphabet == null || alphabet.length == 0) {
return;
}
if (alphabet[0] > sum) {
// no sense to search, since smallest element in array already bigger than sum
return;
} else if (alphabet[0] == sum) {
Set<Integer> subSet = new HashSet<>();
subSet.add(alphabet[0]);
printSubset(subSet);
}
Set<Integer> subSet = new HashSet<>();
processMaximalSubSetToSum(alphabet, sum, 0, 0, subSet);
}
private static void processMaximalSubSetToSum(int[] alphabet, int sum, int sumSoFar, int startFrom, Set<Integer> subSet) {
if (startFrom >= alphabet.length) {
if (isMaximalSubSet(alphabet, subSet, sum - sumSoFar)) {
printSubset(subSet);
}
return;
}
for (int i = startFrom; i < alphabet.length; i++) {
int newSum = sumSoFar + alphabet[i];
if (newSum > sum) {
if (isMaximalSubSet(alphabet, subSet, sum - sumSoFar)) {
printSubset(subSet);
}
return;
} else {
subSet.add(alphabet[i]);
if (newSum == sum) {
printSubset(subSet);
} else {
processMaximalSubSetToSum(alphabet, sum, newSum, i + 1, subSet);
}
subSet.remove(alphabet[i]);
}
}
}
private static boolean isMaximalSubSet(int[] alphabet, Set<Integer> subSet, int diff) {
// search first mismatch element between alphabet and current SubSet
Iterator<Integer> it = subSet.iterator();
int i = 0;
while (it.hasNext()) {
if (it.next() != alphabet[i]) {
break;
}
i++;
}
return i >= alphabet.length || alphabet[i] > diff;
}
private static void printSubset(Set<Integer> subset) {
System.out.println(subset);
}
public static void main(String[] args) throws java.lang.Exception {
//printMaximalSubSetsToSum(new int[]{1, 2, 3, 4, 5}, 7);
// Correct output is: {1, 2, 3}; {1, 2, 4}; {1, 5}; {2, 5}; {3, 4}
}
}
可以'S'包含重复的值？例如'S = {1,2,3,4,5}'？ – Seph 2012-03-11 10:01:37
@Seph，不，它是'set' =没有重复 – dantuch 2012-03-11 10:14:21