虽然回答有些晚，但我认为我已经找到了这个问题的一个简单解决方案。我们使用回溯法按字典顺序枚举集合S的子集，并检查生成的子集的sum。
当sum超过k时，有趣的部分来了：我们需要检查生成的subset是否是先前报告的项目的适当子集。
一种解决方案是保留所有报告的子集并检查包含关系，但这很浪费。
相反，我们计算k和sum之间的差异。如果在S中存在一个元素e，使得e not in subset且e <= (k - sum)，则我们生成的集合是先前报告的子集的适当子集，我们可以安全地跳过它。
下面是使用普通的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}
这是一个幂集问题。最近我发现了这个网站，关于算法的内容让我的想象力激发了起来，因此我提供了幂集/组合的解决方案。您可以直接复制、粘贴并运行程序。
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);
}
}
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}
}
}
一个老问题，但仍然是一个有趣的问题。
这里提供了一个递归的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);
}
非常抱歉我回复晚了。不过这个方案怎么样？
1）从给定的数组/集合构建一个MIN-HEAP结构。
2）从根节点开始遍历该结构，并在访问的节点处减去该节点的值。一旦超过所需的总和（curr_sum > k），输出此路径，回溯到父节点并选择另一条路径（可以递归完成）。
3）如果回溯将您带回到您开始的原始节点，请从根节点-左节点递归实现整个算法。
4）现在使用MAX-HEAP执行相同的步骤（2）和（3）。
我对算法和数据结构还很陌生，只是开始阅读《算法导论-Cormen》。这可能是一个有缺陷的解决方案，但如果有人指出错误，我会非常高兴 :)
S可以包含重复的值吗？例如S = {1, 2, 3, 3, 4, 5}？ - Sephset=没有重复项。 - dantuch