SubsetSumProblemReturnsSubsetValues

********************************* This program RETURNS ALL the subsets if many subsets are present**************
/*
 * 
NOTE: The elements in this array can also be NEGATIVE. The program finds all the subsets even it negative numbers
are present.
Question:Print all subset of a given set which sums up to ZERO 
		{8,3,5,1,-4,-8} 
		so answer will be : {8,-8} 
		{3,5,-8} 
		{3,1,-4} 

Question Source: http://www.careercup.com/forumpost?id=5355201013743616
				 http://www.careercup.com/question?id=12899672
				 http://www.careercup.com/question?id=6241189850251264
	
Solution Source: http://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target


Algorithm:
Perform a recursive DFS - the element from an array can either be or not be in the set, 
hence the solution is O(2^n) time complexity, where n = number of elements in the input array.
Pick one number with index 'i' and check the sum with arrayElement + stack_sum is less than or equal to
the target sum. If yes, then add the element to the stack and also add the element to the stack_sum 

The key point is to keep a track of a sequence of numbers in each recursive call. 
To achieve this one can use a single Stack. The number of elements on the stack corresponds 
on a depth of recursion. Once the elements on the stack sums to Target_Sum the stack is printed out.
However, we still continue with the recursion. 


*/
package SubsetSumProblem;

import java.util.Stack;

public class GetAllSubsetByStack {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 15;    // global & final
    
    private Stack<Integer> stack = new Stack<Integer>();  // global

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;

    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                sumInStack -= (Integer) stack.pop();
            }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }
 
    public static void main(String[] args) {
    	
    	int[] DATA = { 10,5,1,-2,4,3};   // Negative Numbers are also accepted

        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}
/*
Analysis:
	Time Complexity = O(2^n) where n is the number of elements in the input array
	Space Complexity = O(n)
*/
********************************* This program only returns one subset if many subsets are present**************
package SubsetSumProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
NOTE: This program only returns one subset. It does not return all the subsets
 * Question: Find a subset of elements that are selected from a given set whose sum adds
 * up to a given number K. Assume that the set contains non-negative, unique
 * values.
 * 
 * Source: http://www.careercup.com/forumpost?id=5355201013743616
 * 		   https://github.com/kowshik/big-o/blob/master/java/src/general/SubsetSum.java
 *         http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/ <- DONOT FOLLOW THIS SOLUTION. FOLLOW THE SOLUTION MENTIONED BELOW
 */
public class SubsetSum {
	public static List<Integer> findSubsetSum(int[] numbers, int sum) {
		ArrayList<Integer> subset = new ArrayList<Integer>();
		for (int i = 0; i < numbers.length; i++) {
			if (findSubsetSum(numbers, i, subset, sum)) {
				return subset;
			}
		}

		return null;
	}

	private static boolean findSubsetSum(int[] numbers, int index,
			ArrayList<Integer> subset, int sum) {
		if (index >= numbers.length) {
			return false;
		}

		if (sum - numbers[index] == 0) {
			subset.add(numbers[index]);
			return true;
		}

		if (sum - numbers[index] < 0) {
			return false;
		}

		sum -= numbers[index];
		for (int i = index + 1; i < numbers.length; i++) {
			if (findSubsetSum(numbers, i, subset, sum)) {
				subset.add(numbers[index]);
				return true;
			}
		}

		return false;
	}

	public static void main(String[] args) {
		int values[] = { 1,2,3,4,5,6};
		System.out.println(Arrays.toString(values));
		System.out.println(findSubsetSum(values, 10));  // Returns only one subset. Does not return all the subsets
	}
}
/*
Analysis:
	Time Complexity = O()
	Space Complexity = O()
*/