Formatted question description: https://leetcode.ca/all/39.html
39. 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
The same repeated number may be chosen from
candidates unlimited number of times.
- All numbers (including
target) will be positive integers.
- The solution set must not contain duplicate combinations.
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ , [2,2,3] ]
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]
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.
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: