LeetCode | Combination Sum

題目

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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• 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]

  分析

  用遞歸的動態規劃解決，可以加上備忘錄，如果target值允許的話，可以凶殘的用非遞歸的數組方式解決。

  代碼

  import java.util.ArrayList;
  import java.util.Arrays;
  
  public class CombinationSum {
  	public ArrayList> combinationSum(int[] candidates,
  			int target) {
  		Arrays.sort(candidates);
  		ArrayList> results = new ArrayList>();
  		ArrayList list = new ArrayList();
  		solve(results, list, candidates, 0, target);
  		return results;
  	}
  
  	private void solve(ArrayList> results,
  			ArrayList list, int[] candidates, int i, int target) {
  		if (target < 0) {
  			return;
  		}
  		if (target == 0) {
  			results.add(new ArrayList(list));
  			return;
  		}
  		for (int j = i; j < candidates.length && candidates[j] <= target; ++j) {
  			list.add(candidates[j]);
  			solve(results, list, candidates, j, target - candidates[j]);
  			list.remove(list.size() - 1);
  		}
  	}
  }