Finding N Subsets of a List Object to a sum

Question

I am trying to get a list of subsets that sum up to the specified sum and I keep running out if index. Below is my code:

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

And the exception is always thrown at last but two. E.g: If length == 10 it throws if currentIndex == 8.

I keep getting IndexOutOfBoundException. After some time here ListInfo info = data.get(currentIndex); I don't know why. Any help would be appreciated.

EDIT:

this is the way I am calling the method:

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

@OusmaneMahyDiaw Last but two. E.g: If length == 10 it throws at 8 — , Apr 06 '17 at 14:42
to be honest, since we don't know the value "fromIndex" and "endIndex" it will be difficult to figure out the cause, However as you probably already know there are two options either the currentIndex is < 0 || currentIndex > data.length-1. Either way to prevent the exception is easy considering you can guard that block of code with if statements that say "only execute this if it's within the bounds of >=0 && less than data.length" However like i said to find the cause you need to include further details to what I've mentioned. — Ousmane D., Apr 06 '17 at 14:44
@OusmaneMahyDiaw this is the way I've been calling the function `calcBudget(listInfos, 0, listInfos.size() - 1, 0, 45);` — , Apr 06 '17 at 14:46
When you `data.remove(0)`, your list gets shorter. If `endIndex` was the last index before, it now points outside the list. — Ole V.V., Apr 06 '17 at 14:52

score -1 · Answer 1 · answered Apr 06 '17 at 15:04

Without getting to much into the details of your code, what you are doing is basically a filtered power set. One of the classic ways to calculate a power set, is to

Create a Set of Sets (or List of Sets)
Insert the empty set into that result set
For each element of the original collection, iterate over the result set, and make a copy of each of the existing sets with the new element added to them

In your case, you need to add a filter to that, restricting the output to sets that produce the desired sum. Here's a sample implementation:

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

Finding N Subsets of a List Object to a sum

1 Answers1