39. Combination Sum
Combination Sum (LeetCode 39) 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.
- Blind 75 · #37 of 75 · Backtracking
- NeetCode 150 · #69 of 150 · Backtracking
- NeetCode 250 · #125 of 250 · Backtracking
How to solve Combination Sum
Combination Sum is a Combination Sum problem, part of Backtracking Patterns. Find combinations that sum to target using backtracking. Handle reuse and duplicates.
Work towards the solution in these steps:
- Consider using a backtracking approach to explore all possible combinations that sum up to the target.
- Think about how to recursively build combinations by choosing candidates and reducing the target accordingly.
- To avoid duplicates, ensure your recursion does not revisit previous candidates in earlier positions.
The reference solution runs in O(2^T) time and O(T) space.
The Combination Sum solution and editorial walks through the full approach with reference code.
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) time and O(T) 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
Problems related to Combination Sum
Other problems that use the same Combination Sum and Backtracking Patterns techniques:
- Combination Sum II — Medium, same subpattern
- Partition to K Equal Sum Subsets — 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
Combination Sum FAQ
What is the LeetCode number of Combination Sum?
Combination Sum is LeetCode problem 39, rated Medium.
What pattern is used to solve Combination Sum?
Combination Sum is a Combination Sum problem. It belongs to the Backtracking Patterns pattern, in the Combination Sum subpattern.
What is the time complexity of Combination Sum?
The reference solution runs in O(2^T) time and O(T) space.
Which companies ask Combination Sum?
Combination Sum has been reported in interviews at Adobe, Airbnb, Amazon, Apple, Bloomberg, ByteDance, Citadel, eBay, Facebook, Google, LinkedIn, Microsoft and others.