LeetCode #40: Combination Sum II — Solved in Java

Recursive Search, Compressed Value Counts and bonus Custom Sort with Compressed Counts

Image Source

LeetCode 40 Combination Sum II asks for all unique combinations of candidate integers that add up to a given target, where each index in the array can be used at most one time. The candidates array may contain duplicate values, but the final answer must not contain duplicate combinations, so [1, 2, 2] and another [1, 2, 2] built from different indices count as a single result. Input values are positive, output combinations can appear in any order, and each combination is treated as a multiset of values rather than as a sequence with positional meaning. Compared to Combination Sum, candidates here are not guaranteed to be distinct and each index can be used at most once, so handling repeated values and one use per index is the main difference.

Thinking about a Java solution starts with viewing the search space as a tree built over a sorted array, with each node defined by an index in that array, a remaining sum, and the current partial combination. Sorting groups equal values together and lets the code skip repeated values at the same recursion depth so combinations stay unique. From there, a natural plan is to rely on backtracking that moves forward through indices, keeps remaining nonnegative, and records every path that hits exactly zero, while either branching directly on indices or compressing equal values into (value, count) pairs to trim redundant branches and control how many copies of each value are allowed.

Many interview settings allow standard library helpers such as Arrays.sort, and both of the main solutions here rely on that call to order the candidates before backtracking. Anyone preparing for a stricter environment can also look at a third solution I made at the very end of the article, which keeps the same overall strategy but replaces Arrays.sort with a custom sort routine so no built in sorting methods are required.

LeetCode: Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

• 1 <= candidates.length <= 100

• 1 <= candidates[i] <= 50

• 1 <= target <= 30

I often include the full code as a screenshot to make it easier to read on phones since Substack’s code formatting can be tough to follow on smaller screens. Some solutions tend to be much longer than usual like these, so capturing everything in one image isn’t always practical. You can still copy and run the complete solutions below, and at the end of the article you’ll find the same full code again with even more added comments to help follow along.

Solution 1: Recursive Search with Sorting and Duplicate Skips

This solution solves Combination Sum II by sorting the candidates, then running depth first search across indices while tracking a partial combination and a remaining sum. The search only moves forward in the array and applies a duplicate-skip check at each recursion depth, which keeps each index from being reused and makes sure every multiset of values, such as [1, 2, 2], appears at most one time in the result.