Backtracking and finding all subsets of array that equal some value k

Question

I asked question earlier and i thought i understood it when i went to my terminal to code i am once again completely lost. My problem is i have some array say [1,2,3,4] and i need to find all possible combos that will equal a destination value 5.

I understand there is a backtracking approach to this. i am not able to get it as online a lot of solution approaches are going over my head i just need a simple explanation or a step by step trace of a very small array to visualize what's going on.

I have spent the last 12 hours in the library and i feel really depressed now since i am not able to understand it, i would also appreciate a simple approach. Also i am not familiar with many languages other than C or java.

Answer 1

You've got your hands on a variant of the Subset Sum Problem. Unfortunately the problem is NP-Complete, so if you're hoping for a quick (polynomial) solution, you're out of luck.

That said, if your array is fairly small and the values are fairly small, a brute force solution may still be quick enough.

import java.util.Arrays;
import java.util.LinkedList;


public class SubsetSum {

    /** Helper for the power set generating function.
     *  Starts with a partially built powerSet pSet that includes
     *  numbers with index 0 ... i. For every element in the current power set
     *  Create a new array that is equivalent to the existing array plus it has
     *  the i+1th number (n) concatinated on the end.
     * @param pSet - The completed pSet for a smaller set of numbers
     * @param n - The number of add to this pSet.
     * @return a reference to pSet (not necessary to use). When returning,
     * pSet will have double the size it had when the method began.
     */
    private static LinkedList<Integer[]> addNumb(LinkedList<Integer[]> pSet, int n){
        LinkedList<Integer[]> toAdd = new LinkedList<>();
        for(Integer[] arr : pSet){
            Integer[] arr2 = new Integer[arr.length+1];
            for(int i = 0; i < arr.length; i++){
                arr2[i] = arr[i];
            }
            arr2[arr.length] = n;
            toAdd.add(arr2);
        }

        //Add all of the toAdds to the pSet
        pSet.addAll(toAdd);
        return pSet;
    }

    /** Creates the power set for the given array of ints.
     * Starts by creating a set with the empty array, which is an element of every
     * power set. Then adds each number in the input array in turn to build the final
     * power set.
     * @param numbs - the numbers on which to build a power set
     * @return - the power set that is built.
     */
    private static LinkedList<Integer[]> makePowerSet(int[] numbs){
        LinkedList<Integer[]> pSet = new LinkedList<Integer[]>();
        //Add the empty set as the first default item
        pSet.add(new Integer[0]);

        //Create powerset
        for(int n : numbs){
            addNumb(pSet, n);
        }

        return pSet;
    }

    /** Returns the simple integer sum of the elements in the input array */
    private static int sum(Integer[] arr){
        int i = 0;
        for(int a : arr){
            i += a;
        }
        return i;
    }


    /** Brute-forces the subset sum problem by checking every element for the desired sum.
     */
    public static void main(String[] args) {
        int[] numbs = {1,2,3,4,5,6,7,8}; //Numbers to test
        int k = 7;                 //Desired total value

        LinkedList<Integer[]> powerSet = makePowerSet(numbs);

        for(Integer[] arr : powerSet){
            if(sum(arr) == k)
                System.out.println(Arrays.deepToString(arr));
        }
    }

}

Answer 2

Indeed, there is a story about backtracking, etc.

Let's just go with a bit more complex example:

The value we want to reach is 11, and the array is [5,4,8,2,3,6]

Here is one of the possible algorithms:

We will list all the way we find to reach every possible number lesser than or equal to 11 (I won't talk about the structure we use or anything, because I am just explaining the algorithm, not its implementation).

We will start with nothing, and add consider one new number at a time. In this algorithm, I will consider every number in the array is positive, so I won't keep track of reaching numbers higher than the number we want to reach.

So at the beginning we have nothing.

We introduce our first number : 5

We so have one way to reach 5, and it is 5 (or 5+0 if you prefer)

We introduce our second number : 4 The number we can now reach are:

4:{4}
5:{5}
9:{4+5}

We introduce our third number : 8 The number we can now reach are:

4:{4}
5:{5}
8:{8}
9:{4+5}

Nothing more because 8+4 > 11

We introduce our forth number : 2 The number we can now reach are:

2:{2}
4:{4}
5:{5}
6:{4+2}
7:{5+2}
8:{8}
9:{4+5}
10:{8+2}
11:{4+5+2}

We introduce our fifth number : 3 The number we can now reach are:

2:{2}
3:{3}
4:{4}
5:{5 ; 2+3}
6:{4+2}
7:{5+2 ; 4+3}
8:{8 ; 5+3}
9:{4+5 ; 4+2+3}
10:{8+2 ; 5+2+3}
11:{4+5+2 ; 8+3}

We introduce our sixth number : 6 The number we can now reach are:

2:{2}
3:{3}
4:{4}
5:{5 ; 2+3}
6:{4+2 ; 6}
7:{5+2 ; 4+3}
8:{8 ; 5+3 ; 2+6}
9:{4+5 ; 4+2+3 ; 3+6}
10:{8+2 ; 5+2+3 ; 4+6}
11:{4+5+2 ; 8+3 ; 5+6 ; 2+3+6}

Conclusion : there are 4 ways to make 11 : 4+5+2 ; 8+3 ; 5+6 and 2+3+6

Answer 3

Below is some simple (but horribly inefficient) code to solve this problem.

The "backtracking" part of this is implemented via recursion. Ever time you return from a method in Java you "backtrack" through the stack to wherever it was called from. This makes using the call stack to track your "backtrack" state for you really easy.

Here's the basic idea. Let's say I'm searching some array A for the sum n. We start our search in the array at index i=0. Then we try two things:

• Try including the element A[i] in the running sum. We do this by searching the array from index i+1 for the value n-A[i]. We need to record this element in our running list of included elements. We'll call this list of all elements included in our running sum xs.
• Try not including the element A[i] in the running sum. We do this by searching the array from index i+1 for the current value of n. Since we didn't include A[i] we don't need to update xs.

See how we search the whole array for the first case, backtrack and then do the search over again for the second case?

Note that you need to have a preserved copy of xs around after "backtracking" to use in the second search. I think the simplest way to do this with the standard Java library is to undo the changes to xs when you backtrack. So, if you add some element x to the end of xs to do the "with"-search, then simply remove the last element from xs just before you do the "without"-search.

Rather than trying to store all the answers in a datastructure, I just print an answer as soon as I find it. This is also to simplify the logic of this solution.

import java.util.Deque;
import java.util.ArrayDeque;

public class SubarraySums {

    /** Program entry point */
    public static void main(String[] args) {
        int[] array = { 1, 8, 7, 9, 5, 2 };
        findSubarraySums(12, array);
    }

    /** Wrapper function for the search */
    public static void findSubarraySums(int goal, int[] array) {
        // Search the whole array with an empty starting set
        search(goal, new ArrayDeque<Integer>(), array, 0);
    }

    /** Helper for printing an answer */
    private static void printAnswer(Deque<Integer> xs) {
        // Print the sum
        int sum = 0;
        for (int x : xs) sum += x;
        System.out.printf("%d =", sum);
        // Print the elements
        for (int x : xs) {
            System.out.printf(" %d", x);
        }
        System.out.println();
    }

    /**
     * Search the array, starting from index i,
     * for a subset summing to n.
     * The list xs includes all of the elements that are already
     * assumed to be included in this answer
     */
    private static void search(int n, Deque<Integer> xs, int[] array, int i) {
        // Base case: we've reached zero!
        if (n == 0) {
            printAnswer(xs);
            return;
        }
        // Base case: solution not found
        if (n < 0 || i >= array.length) return;
        // Recursive case: try searching with and without current element
        // with:
        xs.addLast(array[i]);
        search(n-array[i], xs, array, i+1);
        // without:
        xs.removeLast();
        search(n, xs, array, i+1);
    }

}

The above code has 6 elements in the array, so it's going to make 2⁶=64 recursive calls to search. That's why it's "super inefficient". But it's also super simple, so that should help you understand it. You should step through the code with your debugger to see what happens, or just trace out the execution on a piece of paper. It should be pretty obvious how the execution "backtracks" up the call stack to try both options (include / not include) during the search.

I used ArrayDeque in the code above to store my xs list simply because the Deque interface has the addLast and removeLast methods. A LinkedList also would have worked (since it also implements the Deque interface). An ArrayList would work too, but you'd need to use add and remove(list.size()-1), which is a bit more verbose.