Combination Sum

mediumFREEBacktrackingBlind 75

Given an array of distinct integers candidates and a target integer target, return all unique combinations where the chosen numbers sum to target. The same number may be chosen unlimited times. Return a list of combinations, where each combination is a list of integers in ascending order and the combinations are sorted lexicographically. The tests print each combination on its own line with its numbers separated by spaces.

Example

Input

2,3,6,7
7

Output

2 2 3
7

Reasoning

Inputs: candidates is the set $\{2, 3, 6, 7\}$ and target is $7$ . Any candidate may be used any number of times.
A combination is a multiset: $2 + 2 + 3$ and $3 + 2 + 2$ are the same answer, written once in ascending order.
Checking sums to 7: $7 = 7$ works on its own. With $6$ the remainder is $1$ , smaller than every candidate, so it fails. Using only $2$ s gives $2+2+2 = 6$ (remainder $1$ ) or $8$ (overshoot). Using $3$ s: $3 + 3 = 6$ leaves $1$ again, but one $3$ leaves $4 = 2 + 2$ , giving $2 + 2 + 3$ .
No other multiset reaches exactly $7$ , so there are two answers: $\{2, 2, 3\}$ and $\{7\}$ .
Output: a list of these combinations, each ascending, ordered lexicographically (first elements, then second, ...). Since $2 < 7$ , 2 2 3 comes before 7, even though it is longer.
Notice that combinations can differ in length, and the result is empty when no multiset hits the target.

Constraints

1 <= len(candidates) <= 30
2 <= candidates[i] <= 40
1 <= target <= 40

Learn this in

BacktrackingDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Word Search IIhard Merge K Sorted Listshard Remove Nth Node From End of Listmedium

Concept primer

Background Knowledge

The Combination Sum problem is a classic example of a backtracking problem, which is a fundamental concept in algorithm design. Backtracking is an algorithmic technique used to solve problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem. This technique is particularly useful for solving problems that involve combinatorial search, where we need to explore all possible combinations of solutions.

In the context of the Combination Sum problem, we are given an array of distinct integers candidates and a target integer target. The goal is to find all unique combinations of numbers that sum up to the target. Since the same number can be chosen unlimited times, we need to use a recursive approach to explore all possible combinations. The key concept here is to understand how to prune the search space by avoiding duplicate combinations and ensuring that the combinations are sorted lexicographically.

The Combination Sum problem also involves constraint satisfaction, where we need to satisfy the constraint that the sum of the chosen numbers equals the target. This constraint is used to guide the search and prune the search space, ensuring that we only explore combinations that are likely to satisfy the constraint. By understanding how to apply these concepts, we can develop an efficient algorithm to solve the Combination Sum problem.

Algorithm/Approach

The general approach to solve the Combination Sum problem involves using a recursive backtracking algorithm. This algorithm works by recursively exploring all possible combinations of numbers that sum up to the target. The algorithm starts by choosing a number from the candidates array and then recursively explores all possible combinations that include the chosen number. If the sum of the chosen numbers exceeds the target, the algorithm backtracks and explores alternative combinations.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty list to store the result combinations
Define a recursive function that takes the current combination, the remaining target, and the starting index as parameters
In the recursive function, iterate over the candidates array starting from the starting index
For each candidate, check if the current combination plus the candidate exceeds the remaining target
If it does not exceed, add the candidate to the current combination and recursively call the function with the updated combination and remaining target
If the remaining target becomes zero, add the current combination to the result list
After the recursive call, remove the last added candidate from the current combination to backtrack and explore alternative combinations

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to prune the search space by not checking if the current combination exceeds the target
Not backtracking correctly, resulting in duplicate combinations or missing combinations
Not sorting the combinations lexicographically, resulting in incorrect output

Time & Space Complexity

The expected time complexity of the solution is $O(N^{T/M} + N \log N)$ , where $N$ is the length of the candidates array, $T$ is the target sum, and $M$ is the minimum value in the candidates array. The space complexity is $O(T/M + N)$ , which is used to store the recursive call stack and the result combinations. Note that the time complexity is exponential in the worst case, but the backtracking approach helps to prune the search space and reduce the number of recursive calls.

solution.py

Python 3.13

Test results