[leetcode]Combination Sum

新博文地址：

[leetcode]Combination Sum

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 (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]

求满足条件的组合，DFS简直掉渣天啊！！慢慢有感觉了

太饿了，要去吃饭了，具体算法不想写了，看不明白请吐槽

 

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

	public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
	    Arrays.sort(candidates);
		for (int i = 0; i < candidates.length; i++) {
			ArrayList<Integer> list = new ArrayList<Integer>();
			dfs(candidates, i, candidates[i], target, list);
		}
		return result;
	}

	private void dfs(int[] candidates, int begin, int sumUntilNow, int target, ArrayList<Integer> list) {
		list.add(candidates[begin]);
		if (sumUntilNow == target) {
			ArrayList<Integer> cpyList = new ArrayList<Integer>(list);
			result.add(cpyList);
			return;
		} else if (sumUntilNow > target) {
			return;
		}

		dfs(candidates, begin, sumUntilNow + candidates[begin], target, list);
		list.remove(list.size() - 1);
		if (begin < candidates.length - 1) {
			for (int i = begin + 1; i < candidates.length; i++) {
				dfs(candidates, i, sumUntilNow + candidates[i], target, list);
				list.remove(list.size() - 1);
			}
		}
	}