Combination Sum II

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array of positive integers candidates and a target value target. Find every **unique** combination of numbers from candidates whose sum is exactly equal to target. The rules are: - Each number in candidates may be used **at most once** in any single combination. (Note that candidates may contain duplicate values, and a duplicate value counts as a separate, usable element.) - A combination is identified by the multiset of values it contains, not by the positions chosen. Two combinations are considered the same if they contain the same values with the same multiplicities, regardless of the order in which those values appear. Return the list of all such combinations. The combinations themselves may be returned in any order, and the numbers inside each combination may be in any order. No combination should be repeated in the output.

Examples

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Each value can be used once per its occurrence. There are two `1`s available, so `[1,1,6]` is valid. The combinations are returned without duplicates.
Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Although three `2`s exist, only two are needed for `[1,2,2]`. The combination `[1,2,2]` is listed only once even though it could be formed using different pairs of the `2`s.
Input: candidates = [4,4,4,4], target = 3
Output: []
No subset of the available numbers sums to 3, so the result is empty.

Constraints

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
  • Each element of `candidates` may be used at most once per occurrence.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems