import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: DavidAnderson
 * Date: 10/11/13
 * Time: 22:23
 * To change this template use File | Settings | File Templates.
 */
public class FindSubsetsThatSumToN {
    public static List<List<Integer>> findSubsetsThatSumToN(int[] arr, int n){
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        for(int i = 0; i < arr.length; i++){
            for(List<Integer> l : findSubsetsThatSumToN(arr, i, n))
                result.add(l);
        }
        return result;
    }
    public static List<List<Integer>> findSubsetsThatSumToN(int[] arr, int begin, int n){
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(n < arr[begin]) return result;
        if(arr[begin] == n){
            List<Integer> oneElement = new LinkedList<Integer>();
            oneElement.add(arr[begin]);
            result.add(oneElement);
            return result;
        }
        else{
            for(int i = 0; i< arr.length; i++){
                List<List<Integer>> childSubsets = findSubsetsThatSumToN(arr, i, n - arr[begin]);
                for(List l : childSubsets){
                    if(!l.isEmpty()){
                        l.add(arr[begin]);
                        result.add(l);
                    }
                }
            }
            return result;
        }
    }
}