# Question

Formatted question description: https://leetcode.ca/all/39.html

# 39. Combination Sum

Medium

## Description

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:
[
,
[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]
]


# Algorithm

### DFS

Such a result requires the return of all the questions that meet the requirements to solve the problem, in all likelihood, it is necessary to use recursion.

And the idea of solving the problem is the same, similar questions include Path Sum II, Subsets II, Permutations, Permutations II, Combinations, etc. Here we add three new variables, start records the current recursive subscript, out is a solution, res saves everything that has been obtained The solution of each time a new recursive function is called, the target at this time must be subtracted from the current array.

### DP

We can also use iterative solutions to create a three-dimensional array dp, where dp[i] represents the set of all solutions whose target number is i+1.

Here i traverse from 1 to target. For each i, create a two-dimensional array cur, and then traverse the candidates array.

• If the number traversed is greater than i, it means that the current and subsequent numbers cannot form i, directly break off.
• Otherwise, if they are equal, the current numbers form an array by themselves and added to cur.
• Otherwise, traverse all the arrays in dp[i-candidates[j]-1]. If the current number is greater than the first element of the array, skip it, because the result is required to be in order. Otherwise, add the current number to the beginning of the array, and put the array into cur.

# Code

Java

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Combination_Sum {

public static void main(String[] args) {
Combination_Sum out = new Combination_Sum();
Solution_dp s = out.new Solution_dp();

//        System.out.println(s.combinationSum(new int[]{2,3,6,7}, 7)); // [[2,2,3],]
System.out.println(s.combinationSum(new int[]{2,3,5}, 8)); // [[2,2,2,2],[2,3,3],[3,5]]
}

class Solution {

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

public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return result;
}

dfs(candidates, target, 0, new ArrayList<Integer>());

return result;
}

private void dfs(int[] candidates, int target, int start, ArrayList<Integer> onePath) {

if (start >= candidates.length || target < 0) { // target<0, assumption is all positive
return;
}

if (target == 0) {
// continue, and possible 1,-1 are next ones
}

for (int i = start; i < candidates.length; i++) {
// System.out.println(i);
dfs(candidates, target - candidates[i], i, onePath);
onePath.remove(onePath.size() - 1);
}
}
}

class Solution_dp {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// for each-target (from 1 to target), its dp[i][j] => so 3-D array dp[][][]
List<List<List<Integer>>> dp = new ArrayList<>();
Arrays.sort(candidates);

for (int i = 1; i <= target; ++i) {
List<List<Integer>> cur = new ArrayList<>();
for (int j = 0; j < candidates.length; ++j) {
if (candidates[j] > i) break;
if (candidates[j] == i) {
ArrayList<Integer> one = new ArrayList<Integer>();
cur.add(one); // @note: one with proper <Integer>, or else unsupoorted operation error
break;
}
for (List<Integer> a : dp.get(i - candidates[j] - 1)) {
if (candidates[j] > a.get(0)) {
continue;
}

ArrayList<Integer> deepCopied = new ArrayList<>(a); // @note: must have
deepCopied.add(0, candidates[j]); // @note: largest at index=0 for the array
}
}
}

return dp.get(dp.size() - 1);
}

}
}

• // OJ: https://leetcode.com/problems/combination-sum/
// Time: O(NlogN)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/14654/accepted-16ms-c-solution-use-backtracking-easy-understand
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& A, int target) {
vector<vector<int>> ans;
vector<int> tmp;
sort(begin(A), end(A));
function<void(int, int)> dfs = [&](int start, int goal) {
if (goal == 0) {
ans.push_back(tmp);
}
for (int i = start; i < A.size() && gaol - A[i] >= 0; ++i) {
tmp.push_back(A[i]);
dfs(i, goal - A[i]);
tmp.pop_back();
}
};
dfs(0, target);
return ans;
}
};

• class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(s, u, t):
if s == target:
ans.append(t[:])
return
if s > target:
return
for i in range(u, len(candidates)):
c = candidates[i]
t.append(c)
dfs(s + c, i, t)
t.pop()

ans = []
dfs(0, 0, [])
return ans

############

class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""

def dfs(candidates, start, target, path, res):
if target == 0:
return res.append(path + [])

for i in range(start, len(candidates)):
if target - candidates[i] >= 0:
path.append(candidates[i])
dfs(candidates, i, target - candidates[i], path, res)
path.pop()

res = []
dfs(candidates, 0, target, [], res)
return res