public class Solution {

	public static void main(String[] args) {

		int[] candidates = { 5, 5, 10, 2, 3 };

		int target = 15;

		List<List<Integer>> res = combinationSum(candidates, target);

		for (List<Integer> list : res) {
			System.out.println(list);
		}
	}

	public static List<List<Integer>> combinationSum(int[] num, int target) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Arrays.sort(num);
		Stack<Integer> stk = new Stack<Integer>();
		findCombination(result, 0, target, stk, num);
		return result;
	}

	private static void findCombination(List<List<Integer>> result, int index,
			int target, Stack<Integer> stk, int[] num) {

		if (target == 0) {
			result.add(new ArrayList<Integer>(stk));
			return;
		} else {
			for (int i = index; i < num.length; i++) {
				if (num[i] > target)
					return;
				stk.push(num[i]);
				findCombination(result, i + 1, target - num[i], stk, num);
				stk.pop();
			}
		}

	}
}