LeetCode #39: Combination Sum — Solved in Java

Recursive Depth First Search and Sorted Candidates

Image Source

Combination Sum on LeetCode asks for all unique combinations of given candidate integers that add to a target value. Candidates are distinct, each number can be chosen any number of times, and any order of the same multiset counts as the same combination, so [2,3,3] and [3,2,3] represent one result. Constraints keep candidate values between 2 and 40, target between 1 and 40, and guarantee fewer than 150 valid combinations for any test case, which keeps output size manageable for backtracking solutions.

Thinking about this problem in Java starts with modeling the search as a tree built from three pieces of state, an index in the candidates array, a remaining sum, and a partial combination. A recursive helper picks a candidate at or after the current index, pushes it into the partial combination, reduces the remaining sum, and recurses, or skips it and advances the index, which prevents reordering from creating duplicates. Guards stop recursion when the remaining sum reaches zero, falls below zero, or the scan runs past the end of the array. Java code typically holds the current combination in a mutable structure such as a list or fixed buffer, copies that structure into the result list when a valid sum is found, and relies on call stack depth proportional to the length of the current combination.

LeetCode: Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

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

Constraints:

• 1 <= candidates.length <= 30

• 2 <= candidates[i] <= 40

• All elements of candidates are distinct.

• 1 <= target <= 40

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 Depth First Search with Index Choices

This solution builds combinations with recursion. At every step it decides whether to skip the current candidate or take it again, while tracking the remaining sum and the current partial combination.