给定一个集合S，查找其和

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

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

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}

给定一个集合S，查找其和<= k的所有最大子集。

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.
• 如果X ={1, 2, 3}是一个解，那么X{1} {2} {3}{1, 2}{2, 3}的所有子集都被省略了。
• Lexicographic ordering may be used to solve it.
• 字典顺序可以用来解决它。

Any ideas how could this be solved?

有什么办法可以解决这个问题吗?

6 个解决方案

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

如果你输入了{1,2,3,4,5}，并且你正在搜索最大子集——你应该从最大的数字开始构建一个树，并且当sum <= k时，所有的树都展开(所以不要停在4-2上，而是下降到1，得到4-2-1)。

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

因此，从5开始的节点是:5-1 / 5-2 -只有这2个节点的和<= 7

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

4: 4-3 / 4-2-1 / 4-1(以前的子集)

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

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

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

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

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

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

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

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

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

我知道答案已经很晚了，但我想我已经找到了一个解决这个问题的简单方法。我们使用回溯法在字典顺序中枚举S的子集，并检查到目前为止生成的子集的总和。

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.

当总和超过k时，有趣的部分就出现了:我们需要检查生成的子集是否是先前报告的项的适当子集。

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.

相反，我们计算k和和的差。如果在S中有一个元素e，而不是在子集和e <= (k - sum)中，那么我们生成的集合就是先前报告的子集的一个适当子集，我们可以安全地跳过它。

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

这是一个完整的老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;
}

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

输出都是字典排序的最大子集，每行一个:

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

#3

This is a powerset problem. Recently I found this website about algorithms and it's been painting my imagination: hence the powerset/combinations solution following. You can simply copy, paste, and run the program.

这是一个powerset问题。最近，我发现了这个关于算法的网站，它一直在描绘我的想象力:因此，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);
}
}

#4

An old question but still an interesting one.

一个老问题，但仍然是一个有趣的问题。

Here's a recursive Java 8 solution, with a "permutational" approach.

这是一个递归的Java 8解决方案，采用了“置换”方法。

Optimized for cleaner and shorter code rather than performance -- for example the sorting and pruning would only need to take place once.

为更干净和更短的代码而不是性能优化——例如，排序和修剪只需要进行一次。

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());
    }
}

To test it:

测试:

public static void main(String[] args) {
    new SubsetFinder()
        .findSubsets(ImmutableList.of(1, 2, 3, 4, 5), 7)
        .forEach(System.out::println);
}

#5

Algorithm is the following:

算法如下:

• Starting from empty subSet.
• 从空的子集。
• Cycle through original array from the beginning (assuming array is already sorted in ascending order) until currentSum is less or equal target sum.
• 从初始数组(假设数组已经按升序排序)循环到当前和小于或等于目标和为止。
• If current element added to currentSum is less than target sum, adding to current subSet current element and running recursion starting from the next element.
• 如果添加到currentSum的当前元素小于目标和，则添加到当前子集当前元素并从下一个元素开始运行递归。
• Breaking current cycle if current sum exceed targetSum.
• 如果当前的总和超过targetSum，就打破当前的循环。
• If we can't add more elements into current subSet, we checking if it is maximal and print it in this case.
• 如果不能在当前子集中添加更多的元素，我们将检查它是否为最大值，并在本例中打印它。
• To determine maximal subSets we can compare original array and current subSet element by element, searching for the first mismatch. If element at first mismatch index is greater than difference between currentSum and targetSum, subSet is maximal and should be printed.
• 为了确定最大子集，我们可以按元素对原始数组和当前子集元素进行比较，搜索第一个不匹配项。如果第一次失配索引的元素大于当前和目标和之间的差值，则子集是最大值，应该打印出来。

Working solution on Java is below:

Java工作解决方案如下:

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}
    }

}

#6

I am sorry for chipping in so late. But how about doing this?

我很抱歉这么晚才来上班。但是这样做怎么样?

1) Build a MIN-HEAP structure from the given array/set

1)从给定的数组/集合构建一个小堆结构

2) traverse the structure from the root and keep subtracting the value at the node that you visit. Once you exceed the required sum (curr_sum > k), output this path, backtrack to the parent and take another path (this can be done recursively).

2)从根中遍历结构，并在访问的节点上继续减去该值。一旦您超过了所需的和(curr_sum > k)，输出此路径，返回到父进程并选择另一条路径(这可以递归地完成)。

3) If backtracking takes you back to the original node that you started from, implement the entire algorithm recursively from root->left node.

3)如果回溯将您带回初始节点，则从根->左节点递归实现整个算法。

4) Do the same two steps (2) and (3) above but with a MAX-HEAP now.

4)执行上面的两个步骤(2)和(3)，但是现在使用MAX-HEAP。

I am new to algorithms and data structures, and have only started reading Intro to Algos-Cormen. This might be a faulty solution, but I would be more than happy if anyone points out the fault to me :)

我对算法和数据结构不太熟悉，只开始读Algos-Cormen的介绍。这可能是一个错误的解决方案，但如果有人指出我的错误，我会非常高兴: