39. Combination Sum

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

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

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

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

---
Related problems
40-combination-sum-ii
46-permutations
47-permutations-ii
78-subsets
90-subsets-ii

---

	class Solution {
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
	List<List<Integer>> ans = new ArrayList<List<Integer>>();
	dfs(candidates, 0, target, new ArrayList<Integer>(), ans);
	return ans;
	}
	public void dfs(int[] candidates, int curr, int target, List<Integer> prefix, List<List<Integer>> ans) {
	if (target == 0) {
	ans.add(new ArrayList<Integer>(prefix));
	return;
	}
	if (target < 0) {
	return;
	}
	for (int i = curr; i < candidates.length; i++) {
	prefix.add(candidates[i]);
	// not i + 1, to allow repetition
	dfs(candidates, i, target - candidates[i], prefix, ans);
	prefix.remove(prefix.size() - 1);
	}
	}
	}

view raw 39.CombinationSumDFSRecursiveBackTracking.java hosted with ❤ by GitHub

	class Solution:
	def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	def dfs(prefix: List[int], i: int, target: int):
	if target == 0:
	ans.append(prefix.copy())
	return
	for j in range(i, len(candidates)):
	if target - candidates[j] >= 0:
	prefix.append(candidates[j])
	dfs(prefix, j, target - candidates[j])
	prefix.pop()
	ans = []
	dfs([], 0, target)
	return ans

view raw 39.CombinationSum.py hosted with ❤ by GitHub