Q:

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

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.

A:

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 26=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.

