Domain 2MediumCORE

Combination Sum

Input: A list of distinct positive integers (candidates) and a target integer (target). Output: A list of lists containing all unique combinations where the sum equals target. Key Constraints & Rules: 1. Unlimited Reuse: Each candidate can be used multiple times in a single combination (e.g., [2, 3] is valid if we use 2 twice). 2. Unique Combinations: Two combinations are considered different only if the frequency of at least one number differs. Order within a list does not matter for uniqueness; thus, [2, 3] and [3, 2] count as the same combination. We must generate each unique set exactly once. 3. Implicit: Since inputs are positive integers (1 <= candidates[i], target), we do not need to handle negative numbers or zero values in candidates.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Backtracking

39. Combination Sum

Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 59.7%


Problem Breakdown

Input: A list of distinct positive integers (candidates) and a target integer (target). Output: A list of lists containing all unique combinations where the sum equals target. Key Constraints & Rules:

  1. Unlimited Reuse: Each candidate can be used multiple times in a single combination (e.g., [2, 3] is valid if we use 2 twice).
  2. Unique Combinations: Two combinations are considered different only if the frequency of at least one number differs. Order within a list does not matter for uniqueness; thus, [2, 3] and [3, 2] count as the same combination. We must generate each unique set exactly once.
  3. Implicit: Since inputs are positive integers (1 <= candidates[i], target), we do not need to handle negative numbers or zero values in candidates.

Intuition

A brute-force approach would try every possible subset of permutations, which is O(N!)O(N!) and includes invalid orderings (e.g., generating [3, 2] after already finding [2, 3]). This leads to massive redundancy.

The key insight for optimization is Backtracking with Index Control.

  1. We build a combination incrementally by adding candidates one at a time.
  2. To avoid duplicates (permutations), we enforce an ordering constraint: once we pick candidates[i], our next recursive step must consider indices ≥i\ge i. This ensures that if we picked index 00 first, subsequent picks come from the same or later indices in the sorted array, preventing [3, 2] when starting with a smaller number.
  3. Sorting for Pruning: Since candidates are positive integers, sorting them allows us to efficiently prune branches where adding a candidate exceeds target. If we encounter a value larger than the remaining target, all subsequent values (being sorted) will also be too large, allowing an immediate loop break (break).

Approach

  1. State: We maintain a recursive function taking (start_index, current_target). The current_path tracks the combination being built.
  2. Preprocessing: Sort the candidates array to enable efficient pruning (early exit from loops when values exceed remaining target). This is computationally cheap (O(Nlog⁡N)O(N \log N)) and crucial for correctness of the break optimization on unsorted inputs.
  3. Base Case: If current_target == 0, we have found a valid sum; append a copy of current_path to results and return (stop this branch).
  4. Recursive Step: Iterate through candidates starting from start_index. For each candidate:
    • Check if adding it keeps the remaining target non-negative (candidate <= current_target). If not, skip or break (since array is sorted) since all subsequent numbers will be larger.
    • Add candidate to path and recurse with same index (allowing reuse).
  5. Backtrack: After returning from recursion, remove the last added element from current_path so it can try other candidates in this loop iteration.

Complexity Analysis

  • Time Complexity: O(N⋅S)O(N \cdot S) where NN is the number of candidates and SS is the maximum depth of valid combinations found (bounded by 150 per constraints). In a theoretical worst case without output limits, it can be exponential relative to target / min(candidates), but practically bounded here. The sorting step adds negligible overhead (O(Nlog⁡N)O(N \log N)).
  • Space Complexity: O(Target/MinCandidate)O(Target / MinCandidate) for the recursion stack depth plus space required to store the resulting combinations in memory (O(OutputSize)O(OutputSize)).

Solution

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    results = []
    
    # Sort candidates to enable pruning optimization (break loop when value > remaining target)
    candidates.sort()
    
    def backtrack(start_index, current_target, path):
        # Base Case 1: Target reached exactly
        if current_target == 0:
            results.append(path[:])
            return
        
        # Iterate through candidates starting from start_index to enforce order uniqueness
        for i in range(start_index, len(candidates)):
            candidate = candidates[i]
            
            # Pruning: If adding this number exceeds target, stop (since array is sorted)
            if current_target - candidate < 0:
                break
            
            # Choose: Add to path and recurse with same index for unlimited reuse
            path.append(candidate)
            backtrack(i, current_target - candidate, path)
            
            # Un-choose: Backtrack by removing the last element
            path.pop()

    backtrack(0, target, [])
    return results

# Example usage:
# print(combinationSum([2,3,6,7], 7)) 

Edge Cases Handled

  • Target < Smallest Candidate: The loop condition current_target - candidate < 0 ensures we don’t recurse with negative targets. If no candidates fit the target initially or during recursion, results remain empty ([]).
  • No Valid Combinations Found: Returns an empty list immediately if base case is never hit.
  • Exact Match on Last Step: When current_target == 0, we append and return correctly without attempting to add more numbers (preventing [2,3] from becoming [2,3, ...]).
  • Single Candidate Matches Target: The loop runs once, recurses until target is hit or exhausted. If it hits exactly, result contains the single-element list repeated as needed by reuse logic.