# 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, see the code as follows:

Java