https://leetcode.com/problems/combination-sum/

Combination_Sum.java

//https://leetcode.com/problems/combination-sum/
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

		List<List<Integer>> result = new ArrayList<List<Integer>>();

		if (candidates == null || candidates.length == 0)
			return result;

		ArrayList<Integer> current = new ArrayList<Integer>();

		Arrays.sort(candidates);

		/**
		 * depth-first search(DFS).
		 * To solve DFS problem, recursion is a normal implementation.
		 * Note that the candidates array is not sorted, we need to sort it
		 * first.
		 */
		combinationSum(candidates, target, 0, current, result);

		return result;
	}

	/**
	 * 
	 * @param candidates 候选元素
	 * @param target 目标和
	 * @param j index
	 * @param curr 当前集合
	 * @param result 结果集合
	 */
	public void combinationSum(int[] candidates, int target, int j, ArrayList<Integer> curr, List<List<Integer>> result) {
		if (target == 0) {
			ArrayList<Integer> temp = new ArrayList<Integer>(curr);
			result.add(temp);
			return;
		}
		for (int i = j; i < candidates.length; i++) {
			if (target < candidates[i])
				return;
			curr.add(candidates[i]);
			combinationSum(candidates, target - candidates[i], i, curr, result);
			curr.remove(curr.size() - 1);
		}
	}
}