Combination Sum @LeetCode

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Thought: Same as subsets, condition is sum == target, if sum < target, go recursion
	* The most importance is the next number should be gotten from current i, so, helper(xxx, i) but not i+1,
	* i + 1 can not get the same number.
	*
	* In addition: remember to sort the int array at first!!!
	*
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class CombinationSum {
	public static void main(String args[]) {
	int[] candidates = {8, 7, 4, 3};
	int target = 11;
	System.out.println(combinationSum(candidates, target));
	}
	public static ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
	Arrays.sort(candidates);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	combinationSumHelper(result, list, candidates, target, 0);
	return result;
	}
	private static void combinationSumHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] candidates, int target, int position) {
	int sum = 0;
	for (int x: list) {
	sum += x;
	}
	if (sum == target) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	if (sum < target) {
	for (int i = position; i < candidates.length; i++) {
	list.add(candidates[i]);
	combinationSumHelper(result, list, candidates, target, i);
	list.remove(list.size() - 1);
	}
	}
	}
	}

view raw CombinationSum.java hosted with ❤ by GitHub