nSum.java

import java.util.ArrayList;

/**
Given a sum, and a list of non-unique integer, find a combo that sums up to that target, or the closest.
Eg [2, 3, 3, 4], target = 5
O/p = [2, 3]
[2, 3, 3, 4], target = 8
O/p = [2, 3, 3]
[2, 3, 3, 4], target = 15
O/p = [2, 3, 3, 4]
*/

public class nSum {
	private ArrayList<Integer> res;
	private int maxSumSeen;

	public ArrayList<Integer> nSumSolution(int[] nums, int target) {
		res = new ArrayList<>();
		nSumHelper(nums, target, 0, 0, new ArrayList<>());
		return res;
	}

	/***
	 * The algorithm uses backtracking method to find the target list, that is,
	 * it adds the number at the idx to the list, checks if we can find the target(or closest)
	 * then removes the number and moves on to the next idx.
	 * 
	 * This algorithm is exponential in time;
	 * Worst case (n^t) where n = number of elements in array and t is the target num;
	 * 
	 * It sure would need some optimization.
	 * 
	 * @param nums
	 * @param target
	 * @param i current array index
	 * @param curSum running sum of the iteration
	 * @param list running result list
	 */
	private void nSumHelper(int[] nums, int target, int i, int curSum, ArrayList<Integer> list) {
		// if we get a sum that equals the target, stop searching
		if (curSum == target) {
			res = new ArrayList<>(list);
			return;
		}

		// check if curSum is greater than what we've seen so far and store the possible combination
		if (curSum > maxSumSeen) {
			res = new ArrayList<>(list);
		}

		for (int j = i; j < nums.length; j++) {
			// if adding the num will not become bigger than target
			if (curSum + nums[i] <= target) {
				list.add(nums[i]);
				nSumHelper(nums, target, i+1, curSum + nums[i], list);
				list.remove(list.size() - 1); // backtrack
			}
		}
	}

	public static void main(String[] args) {
		nSum test = new nSum();

		int[] ip = new int[] { 2, 3, 3, 4 };
		int target = 8;

		ArrayList<Integer> res = test.nSumSolution(ip, target);

		System.out.print('[');
		for (int i = 0; i < res.size(); i++) {
			System.out.print(res.get(i));
			if (i != res.size() - 1) System.out.print(", ");
		}
		System.out.print(']');
	}
}