How to Solve Combination Sum

This problem requires enumerating all valid combinations from a set of distinct integers that add up to a given target. The key technique is backtracking with pruning to avoid unnecessary recursion. GhostInterview guides you through candidate selection, branch cutting, and result collection for accurate solutions quickly.

Problem Statement

Given a list of distinct integers called candidates and a target integer, return all unique combinations where chosen numbers sum to the target. Each candidate may be used multiple times, and the order of combinations does not matter.

Two combinations are considered unique if at least one number appears a different number of times. The total number of valid combinations is guaranteed to be less than 150, ensuring the backtracking search completes efficiently under these constraints.

Examples

Example 1

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

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 details omitted.

Example 3

Input: candidates = [2], target = 1

Output: []

Example details omitted.

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

Solution Approach

Sort Candidates and Initialize Backtracking

Sort the array to allow early termination when the cumulative sum exceeds the target. Begin backtracking with an empty path and the starting index at 0, ensuring each recursive call considers candidates at or after the current index.

Recursive Backtracking with Pruning

For each candidate, add it to the current path and recursively attempt to reach the target. If the path sum exceeds the target, immediately backtrack. Reuse candidates by allowing recursive calls to continue from the current index instead of incrementing it.

Collect and Return Valid Combinations

Whenever the cumulative sum equals the target, add a copy of the current path to the results. Continue exploring other combinations by backtracking, removing the last candidate, and trying the next option in the loop.

Complexity Analysis

Time complexity depends on the number of valid combinations and recursion depth, which is influenced by the target value and candidate magnitudes. Space complexity is driven by recursion stack depth and storage of all valid combinations.

What Interviewers Usually Probe

• Checks if you handle repeated use of candidates correctly.
• Observes whether you prune branches when the cumulative sum exceeds the target.
• Evaluates if you maintain the uniqueness of combinations without extra structures.

Common Pitfalls or Variants

Common pitfalls

• Failing to prune when the path sum exceeds the target, causing unnecessary recursion.
• Modifying the path in place without restoring it, leading to incorrect combinations.
• Incrementing the index too early and missing valid repeated candidate combinations.

Follow-up variants

• Limit each candidate to be used at most once, changing the backtracking logic to increment the index after use.
• Return combinations in non-descending order and remove duplicates, requiring sorting and skipping duplicates.
• Find combinations whose sum is closest to a target without exceeding it, needing additional tracking of best sums.

How GhostInterview Helps

• Automatically structures recursive backtracking with proper pruning to prevent redundant exploration.
• Highlights candidate reuse mechanics and ensures all unique combinations are captured.
• Analyzes path construction and branch termination to reduce common mistakes in recursion and accumulation.

Topic Pages

• Array
• Backtracking

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

Can a candidate number be used multiple times in Combination Sum?

Yes, each number can be chosen unlimited times, which is why backtracking needs to continue from the current index rather than moving forward.

How does pruning improve the backtracking performance?

Pruning stops recursion once the path sum exceeds the target, preventing exploration of invalid combinations and reducing time complexity.

Are the combinations in any specific order?

No, the problem allows returning combinations in any order as long as each combination itself reflects the correct counts of candidates.

What is the key failure mode in this problem?

A common failure is incorrectly handling repeated candidates or failing to backtrack properly, leading to missing or duplicated combinations.

How is the backtracking pattern applied in Combination Sum?

Backtracking explores each candidate recursively, reuses candidates as needed, and prunes paths exceeding the target to efficiently enumerate all valid combinations.