将列表对象的 N 个子集查找为总和

Question

我正在尝试获取一个子集列表，这些子集的总和达到指定的总和，如果索引，我就会一直用完。下面是我的代码：

private void calcBudget(List<ListInfo> data, int fromIndex, int endIndex, int sumInStack, float target) {
    AppUtils.log(TAG, "Begining: " + fromIndex);
    if (sumInStack == target) {
      AppUtils.log(TAG, "TotalSize: " + stackInfo.size());
    }
    for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
      ListInfo info = data.get(currentIndex);
      Price currentPrice = info.getPrices().get(0);
      if (sumInStack + currentPrice.getPrice() <= target) {
        stackInfo.add(data.get(currentIndex));
        sumInStack += currentPrice.getPrice();
        calcBudget(data, currentIndex+1, endIndex, sumInStack, target);
        Price toPopPrice = data.get(0).getPrices().get(0);
        sumInStack -= toPopPrice.getPrice();
        data.remove(0);
      }
    }
  }

并且总是最后抛出异常，但只有两个。例如：如果长度 == 10，则抛出当前索引 == 8。

我不断收到IndexOutOfBoundException。在这里呆了一段时间ListInfo info = data.get(currentIndex);我不知道为什么。任何帮助将不胜感激。

编辑：

这是我调用该方法的方式：

calcBudget(listInfos, 0, listInfos.size() - 1, 0, 45);

Answer 1

在不深入了解

代码细节的情况下，您正在做的基本上是一个过滤后的电源集。计算功率集的经典方法之一是

• 创建一组集(或集列表(
• 将空集插入到该结果集中
• 对于原始集合的每个元素，循环访问结果集，并创建每个现有集的副本，并向其中添加新元素

在您的情况下，您需要添加一个过滤器，将输出限制为产生所需总和的集合。下面是一个示例实现：

public static Set<Set<Integer>> powerSetWithSum(Set<Integer> source, int sum) {
    Set<Set<Integer>> result = new LinkedHashSet<>();
    result.add(Collections.<Integer>emptySet());
    for (Integer integer : source) {
        Set<Set<Integer>> tmp = new LinkedHashSet<>();
        for (Set<Integer> set : result) {
            Set<Integer> copy = new LinkedHashSet<>(set);
            copy.add(integer);
            // optimization to save time and space
            if (copy.stream().mapToInt(Integer::valueOf).sum() <= sum) {
                tmp.add(copy);
            }
        }
        result.addAll(tmp);
    }
    return result.stream()
                 .filter((s) -> s.stream().mapToInt(Integer::intValue).sum() == sum)
                 .collect(Collectors.toSet());
}