Recursion and Backtracking Generating every choice
321. Combination Sum
You are given an array nums of different positive integers and a positive integer target. Return every
combination of values from nums that adds up to target. A combination may use the same value any
number of times.
A combination is a list of values in which order does not matter, so [2,7] and [7,2] are the same
combination and you return it once. Two combinations are different when some value appears a different
number of times in them. If no combination adds up to target, return an empty list.
The combinations can come back in any order, and so can the values inside each one. Any order is accepted. The examples list each combination's values from smallest to largest and sort the combinations.
Example 1
Input: nums = [4, 2, 7, 3], target = 9
[[2,2,2,3],[2,3,4],[2,7],[3,3,3]]Explanation: Four combinations add up to 9: 2 + 2 + 2 + 3, 2 + 3 + 4, 2 + 7 and 3 + 3 + 3. The first and the last use one value several times, which is allowed.
Example 2
Input: nums = [6, 1], target = 6
[[1,1,1,1,1,1],[6]]Explanation: The value 1 can be used six times, and 6 on its own is a combination too. Mixing them does not work, because 6 + 1 is already more than 6.
Example 3
Input: nums = [8, 4, 10], target = 15
[]Explanation: Every value is even, so every combination adds up to an even number, and 15 is odd. The answer is an empty list.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1051 ≤ nums[i] ≤ 109- All the values in
numsare different. 1 ≤ target ≤ 30
Clarifying questions
What you would ask an interviewer before writing any code.