Variant of subset sum

Question

I read through all subset sum topics and still have issues with implementing the algorithm for the following problem.

Given the array A of N integers (N<=20) where

• a[i]<=20
• values do not have to be unique

and an integer K (K<=20).

Rules:

• Array items equal to K are "covered" with K.
• If sum of two or more array numbers is equal to K, these numbers are also covered.
• Each number in the array can be covered only once.

Example:

N=6, integers: 1, 1, 2, 3, 4, 5

K=4

Possible coverages:

1. coverage
   • 4 is covered.
   • 1, 1, 2 are covered as 1+1+2=4.
2. coverage
   • 4 is covered.
   • 1, 3 are covered as 1+3=4.

K=5

Possible coverages:

1. coverage
   • 5 is covered.
   • 1,1,3 are covered as 1+1+3=5.
2. coverage
   • 5 is covered.
   • 1,4 are covered as 1+4=5.
   • 2,3 are covered as 2+3=5.

Goal:

For given array A and integer K, find all possible "coverages". I need all coverages, not only one which covers most of the array items.

I have tried with two approaches:

1. Brut force algorithm. Checking all possible subsets of all possible sizes works, but takes too much time even for only 10 numbers. I need it to finish in no more than 500ms.
2. First, I sorted the array in descending order. Then for each possible number of sub-sums I create "slots". I loop through the array and put numbers in the slots following the rules like:
   • Put number in the slot if its sum becomes equal to K.
   • Put number in the slot having the least sum of all slots.
   • Put number in the slot which gives the closet sum to K of all slots.

Well, the second approach works and works fast. But I found scenarios where some coverages are not found.

I would appreciate if somebody offered idea for solving this problem.

I hope I explained the problem well.

Thanks.

Answer 1

I don't have ready answer for that, but I recommend to take a look on 'Bin packing problem' it could be usefull here.

The main problem is to find all possible sums giving number K. So try this:

Collection All_Possible_Sums_GivingK;

find_All_Sums_Equal_To_K(Integer K, Array A)
{
    /* this function after finding result
    add it to global Collection AllPossibleSumsGivingK; */
    find_All_Elements_Equal_To_K(Integer K, Array A); 

    Array B = Remove_Elements_Geater_Or_Equal_To_K(Integer K, Array A);

    for all a in A {
        find_All_Sums_Equal_To_K(Integer K-a, Array B-a) 
    }
} 

Answer 2

I modified this from an earlier answer I gave to a different subset sum variant: https://stackoverflow.com/a/10612601/120169

I am running it here on the K=8 case with the above numbers, where we reuse 1 in two different places for one of the two "coverages". Let me know how it works for you.

public class TurboAdder2 {
    // Problem inputs
    // The unique values
    private static final int[] data = new int[] { 1, 2, 3, 4, 5 };
    // counts[i] = the number of copies of i
    private static final int[] counts = new int[] { 2, 1, 1, 1, 1 };
    // The sum we want to achieve
    private static int target = 8;

    private static class Node {
        public final int index;
        public final int count;
        public final Node prevInList;
        public final int prevSum;
        public Node(int index, int count, Node prevInList, int prevSum) {
            this.index = index;
            this.count = count;
            this.prevInList = prevInList;
            this.prevSum = prevSum;
        }
    }

    private static Node sums[] = new Node[target+1];

    // Only for use by printString and isSolvable.
    private static int forbiddenValues[] = new int[data.length];

    private static boolean isSolvable(Node n) {
        if (n == null) {
            return true;
        } else {
            while (n != null) {
                int idx = n.index;
                // We prevent recursion on a value already seen.
                // Don't use any indexes smaller than lastIdx
                if (forbiddenValues[idx] + n.count <= counts[idx]) {
                    // Verify that none of the bigger indexes are set
                    forbiddenValues[idx] += n.count;
                    boolean ret = isSolvable(sums[n.prevSum]);
                    forbiddenValues[idx] -= n.count;
                    if (ret) {
                        return true;
                    }
                }
                n = n.prevInList;
            }
            return false;
        }
    }

    public static void printString(String prev, Node n, int firstIdx, int lastIdx) {
        if (n == null) {
            printString(prev +" |", sums[target], -1, firstIdx);
        } else {
            if (firstIdx == -1 && !isSolvable(sums[target])) {
                int lidx = prev.lastIndexOf("|");
                if (lidx != -1) {
                    System.out.println(prev.substring(0, lidx));
                }
            }
            else {
                while (n != null) {
                    int idx = n.index;
                    // We prevent recursion on a value already seen.
                    // Don't use any indexes larger than lastIdx
                    if (forbiddenValues[idx] + n.count <= counts[idx] && (lastIdx < 0 || idx < lastIdx)) {
                        // Verify that none of the bigger indexes are set
                        forbiddenValues[idx] += n.count;
                        printString((prev == null ? "" : (prev + (prev.charAt(prev.length()-1) == '|' ? " " : " + ")))+data[idx]+"*"+n.count, sums[n.prevSum], (firstIdx == -1 ? idx : firstIdx), idx);
                        forbiddenValues[idx] -= n.count;
                    }
                    n = n.prevInList;
                }
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < data.length; i++) {
            int value = data[i];
            for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) {
                for (int newsum = sum+1; newsum <= target; newsum++) {
                    if (sums[newsum - sum] != null) {
                        sums[newsum] = new Node(i, count, sums[newsum], newsum - sum);
                    }
                }
            }
            for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) {
                sums[sum] = new Node(i, count, sums[sum], 0);
            }
        }
        printString(null, sums[target], -1, -1);
    }
}