Combination Sum

Combination Sum is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Combination Sum subpattern.

Problem statement

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

Topics and companies

Topics: Array, Backtracking.

Reported in interviews at Adobe, Airbnb, Amazon, Apple, Bloomberg, ByteDance, Citadel, eBay, Facebook, Google, LinkedIn, Microsoft and others.

How to practise Combination Sum on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(2^T), where T = target. Each recursive call can branch into two: include or exclude a candidate, and the number of combinations is bounded by the number of ways to sum to target. time and O(T), where T = target, for the recursion stack and current combination. The output space is O(K*L), where K is the number of combinations and L is the average length of a combination. space.

Open Combination Sum in the code editor, or read the Combination Sum editorial for a worked solution with its approach and complexity analysis.

Where Combination Sum sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• Combination Sum subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Combination Sum

Other problems that use the same Combination Sum and Backtracking Patterns techniques:

• Combination Sum II — Medium, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Generate Parentheses — Medium, same pattern
• Letter Combinations of a Phone Number — Medium, same pattern
• Next Permutation — Medium, same pattern