Practice/LinkedIn/Leetcode 40. Combination Sum II

Leetcode 40. Combination Sum II

CodingMust

Problem

You are given a collection of candidate numbers and a target value. Your task is to find all distinct combinations of candidates where the chosen numbers sum to the target.

Important considerations:

• The same number may appear multiple times in the input collection
• Each number from the input may be used at most once in each combination
• The solution set must not contain duplicate combinations
• You may return the combinations in any order

Requirements

1. Find all valid combinations where numbers sum exactly to the target
2. Each element from the input array can only be used once per combination
3. Avoid duplicate combinations in the result (e.g., [1, 2] and [2, 1] are considered the same)
4. Return an empty list if no valid combinations exist

Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30
• All numbers are positive integers

Examples

Example 1:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]] Explanation: The four unique combinations that sum to 8 are shown above

Example 2:

Input: candidates = [2, 5, 2, 1, 2], target = 5 Output: [[1, 2, 2], [5]] Explanation: We can use 1 and two 2s, or the single 5

Example 3:

Input: candidates = [1], target = 2 Output: [] Explanation: No combination can reach the target