Combination Sum II

Combination Sum II 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 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

Topics and companies

Topics: Array, Backtracking.

Reported in interviews at Amazon, Uber, Microsoft, ByteDance.

How to practise Combination Sum II 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^n), where n is the number of candidates. This is because in the worst case, each candidate can be either included or excluded, leading to exponential combinations. Sorting takes O(n log n), but the backtracking dominates. time and O(k * n), where k is the number of valid combinations and n is the average length of each combination. The recursion stack can go up to O(n) deep. space.

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

Where Combination Sum II 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 II

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

• Combination Sum — 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