Recursion and Backtracking Generating every choice
322. Combination Sum II
You are given an array of positive integers nums and a positive integer target. Return every
combination of elements of nums whose values add up to exactly target. A combination uses each
element at most once, and you return it as the list of its values.
nums can hold the same value more than once. A value can appear in a combination as many times as it
appears in nums, and no more. Return each combination once. Two combinations are the same when they hold
the same values the same number of times, even if the values come from different positions.
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. If no
combination adds up to target, return an empty list.
Example 1
Input: nums = [3, 1, 5, 1, 4, 2, 2], target = 6
[[1,1,2,2],[1,1,4],[1,2,3],[1,5],[2,4]]Explanation: Five combinations add up to 6, and [1,5] is listed once although either 1 can be used. [3,3] and
[2,2,2] do not count, because nums holds only one 3 and two 2s.
Example 2
Input: nums = [2, 2, 2, 2, 2], target = 6
[[2,2,2]]Explanation: Any three of the five 2s add up to 6. There are ten ways to pick their positions, but all ten give the same values, so the combination is listed once.
Example 3
Input: nums = [6, 7, 10], target = 5
[]Explanation: Every number is larger than 5, so no combination reaches it and 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 ≤ 1001 ≤ nums[i] ≤ 501 ≤ target ≤ 35
Clarifying questions
What you would ask an interviewer before writing any code.