1. Description

Given a set of candidate numbers (C) (without duplicates) 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.
The solution set must not contain duplicate combinations.

2. Runtime Distribution

3. Submission Details

4. Example

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

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public List> combinationSum(int[] candidates, int target) {
	List> results = new ArrayList>();
	if (candidates == null || candidates.length == 0 || target <= 0) {
		return results;
	}
	LinkedList records = new LinkedList();
	dfs(candidates, 0, records, results, target);
	return results;
}

private void dfs(int[] candidates, int start, LinkedList records, List> results,
		int target) {
	if (target == 0) {
		results.add(new LinkedList(records));
	}
	if (target <= 0) {
		return;
	}
	for (int i = start; i < candidates.length; i++) {
		records.offer(candidates[i]);
		dfs(candidates, i, records, results, target - candidates[i]);
		records.pollLast();
	}
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode0039 {
	public List> combinationSum(int[] candidates, int target) {
		List> results = new ArrayList>();
		if (candidates == null || candidates.length == 0 || target <= 0) {
			return results;
		}
		LinkedList records = new LinkedList();
		dfs(candidates, 0, records, results, target);
		return results;
	}

	private void dfs(int[] candidates, int start, LinkedList records, List> results,
			int target) {
		if (target == 0) {
			results.add(new LinkedList(records));
		}
		if (target <= 0) {
			return;
		}
		for (int i = start; i < candidates.length; i++) {
			records.offer(candidates[i]);
			dfs(candidates, i, records, results, target - candidates[i]);
			records.pollLast();
		}
	}

	public static void main(String[] args) {
		LeetCode0039 leetcode = new LeetCode0039();
		int[] candidates = { 2, 3, 6, 7 };
		List> results = leetcode.combinationSum(candidates, 7);
		for (int i = 0; i < results.size(); i++) {
			for (int j = 0; j < results.get(i).size(); j++) {
				System.out.print(results.get(i).get(j) + " ");
			}
			System.out.println();
		}
	}
}

[/restab]
[/restabs]