Combination Sum

This question is asked by Apple. Given a list of positive numbers without duplicates and a target number, find all unique combinations of the numbers that sum to the target.

Note: You may use the same number more than once.

Example(s)

Example 1:

Input: numbers = [2, 4, 6, 3], target = 6
Output: [
    [2, 2, 2],
    [2, 4],
    [3, 3],
    [6]
]
Explanation:
Combination 1: 2 + 2 + 2 = 6
Combination 2: 2 + 4 = 6
Combination 3: 3 + 3 = 6
Combination 4: 6 = 6

Example 2:

Input: numbers = [2, 3, 6, 7], target = 7
Output: [
    [2, 2, 3],
    [7]
]
Explanation:
Combination 1: 2 + 2 + 3 = 7
Combination 2: 7 = 7

Example 3:

Input: numbers = [2], target = 1
Output: []
Explanation:
Cannot form target 1 with number 2 (even using multiple times).

Example 4:

Input: numbers = [1], target = 2
Output: [[1, 1]]
Explanation:
Can use 1 twice: 1 + 1 = 2

Solution

The solution uses Backtracking (DFS):

1. Sort numbers: Sort in ascending order to avoid duplicates
2. Backtracking: For each number, try using it (can use multiple times)
3. Recursive search: Recursively find combinations for remaining target
4. Avoid duplicates: Only consider numbers from current index onwards

JavaScript Solution

JavaScript Solution - Backtracking

/**
* Find all unique combinations that sum to target
* @param {number[]} numbers - Array of positive numbers
* @param {number} target - Target sum
* @return {number[][]} - All unique combinations
*/
function combinationSum(numbers, target) {
const result = [];
const current = [];

// Sort numbers to avoid duplicates and enable early termination
const sorted = [...numbers].sort((a, b) => a - b);

/**
 * Backtracking function
 * @param {number} start - Start index (to avoid duplicates)
 * @param {number} remaining - Remaining target sum
 */
function backtrack(start, remaining) {
  // Base case: found a valid combination
  if (remaining === 0) {
    result.push([...current]);
    return;
  }
  
  // Try each number starting from 'start' index
  for (let i = start; i < sorted.length; i++) {
    const num = sorted[i];
    
    // Early termination: if current number is too large, skip
    if (num > remaining) {
      break; // Since sorted, all remaining numbers are also too large
    }
    
    // Use this number
    current.push(num);
    
    // Recursively search with remaining target
    // Use 'i' (not 'i+1') because we can reuse the same number
    backtrack(i, remaining - num);
    
    // Backtrack: remove last added number
    current.pop();
  }
}

backtrack(0, target);
return result;
}

// Test cases
console.log('Example 1:', combinationSum([2, 4, 6, 3], 6)); 
// [[2,2,2], [2,4], [3,3], [6]]

console.log('Example 2:', combinationSum([2, 3, 6, 7], 7)); 
// [[2,2,3], [7]]

console.log('Example 3:', combinationSum([2], 1)); 
// []

console.log('Example 4:', combinationSum([1], 2)); 
// [[1,1]]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Backtracking

from typing import List

def combination_sum(numbers: List[int], target: int) -> List[List[int]]:
  """
  Find all unique combinations that sum to target
  
  Args:
      numbers: Array of positive numbers
      target: Target sum
      
  Returns:
      List[List[int]]: All unique combinations
  """
  result = []
  current = []
  
  # Sort numbers to avoid duplicates and enable early termination
  sorted_numbers = sorted(numbers)
  
  def backtrack(start: int, remaining: int):
      """
      Backtracking function
      
      Args:
          start: Start index (to avoid duplicates)
          remaining: Remaining target sum
      """
      # Base case: found a valid combination
      if remaining == 0:
          result.append(current[:])
          return
      
      # Try each number starting from 'start' index
      for i in range(start, len(sorted_numbers)):
          num = sorted_numbers[i]
          
          # Early termination: if current number is too large, skip
          if num > remaining:
              break  # Since sorted, all remaining numbers are also too large
          
          # Use this number
          current.append(num)
          
          # Recursively search with remaining target
          # Use 'i' (not 'i+1') because we can reuse the same number
          backtrack(i, remaining - num)
          
          # Backtrack: remove last added number
          current.pop()
  
  backtrack(0, target)
  return result

# Test cases
print('Example 1:', combination_sum([2, 4, 6, 3], 6))  
# [[2, 2, 2], [2, 4], [3, 3], [6]]

print('Example 2:', combination_sum([2, 3, 6, 7], 7))  
# [[2, 2, 3], [7]]

print('Example 3:', combination_sum([2], 1))  
# []

print('Example 4:', combination_sum([1], 2))  
# [[1, 1]]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

• Time Complexity: O(2^N) - Where N is the number of combinations. In the worst case, we explore all possible combinations. The actual complexity depends on the target and numbers.
• Space Complexity: O(target) - For the recursion stack (worst case when using smallest number repeatedly) and current combination.

Approach

The solution uses Backtracking (DFS):

1. Sort numbers:

   • Sort in ascending order
   • This helps avoid duplicate combinations and enables early termination

2. Backtracking function:

   • backtrack(start, remaining): Find combinations for remaining target
   • start: Index to start from (avoids duplicates)
   • remaining: Remaining target sum

3. For each number:

   • If number > remaining: Skip (early termination, since sorted)
   • Add number to current combination
   • Recursively search with remaining - num
   • Use i (not i+1) as start index because we can reuse numbers
   • Backtrack by removing the number

4. Base case:

   • When remaining === 0, we found a valid combination
   • Add current combination to results

Key Insights

• Backtracking: Explore all possible combinations
• Can reuse numbers: Use i instead of i+1 in recursive call
• Sort first: Avoids duplicates and enables early termination
• Early termination: If number > remaining, skip (since sorted)
• O(2^N) time: Explores all combinations in worst case

Step-by-Step Example

Let's trace through Example 1: numbers = [2, 4, 6, 3], target = 6

numbers = [2, 4, 6, 3]
Sorted: [2, 3, 4, 6]
target = 6

backtrack(0, 6):
  start = 0, remaining = 6
  
  i=0: num=2, 2 <= 6
    current = [2]
    backtrack(0, 4):
      start = 0, remaining = 4
      i=0: num=2, 2 <= 4
        current = [2, 2]
        backtrack(0, 2):
          start = 0, remaining = 2
          i=0: num=2, 2 <= 2
            current = [2, 2, 2]
            backtrack(0, 0):
              remaining = 0 → add [2,2,2] to result
            current.pop() → [2, 2]
          i=1: num=3, 3 > 2, break
        current.pop() → [2]
      i=1: num=3, 3 <= 4
        current = [2, 3]
        backtrack(1, 1):
          start = 1, remaining = 1
          i=1: num=3, 3 > 1, break
        current.pop() → [2]
      i=2: num=4, 4 <= 4
        current = [2, 4]
        backtrack(2, 0):
          remaining = 0 → add [2,4] to result
        current.pop() → [2]
      i=3: num=6, 6 > 4, break
    current.pop() → []
  
  i=1: num=3, 3 <= 6
    current = [3]
    backtrack(1, 3):
      start = 1, remaining = 3
      i=1: num=3, 3 <= 3
        current = [3, 3]
        backtrack(1, 0):
          remaining = 0 → add [3,3] to result
        current.pop() → [3]
      i=2: num=4, 4 > 3, break
    current.pop() → []
  
  i=2: num=4, 4 <= 6
    current = [4]
    backtrack(2, 2):
      start = 2, remaining = 2
      i=2: num=4, 4 > 2, break
    current.pop() → []
  
  i=3: num=6, 6 <= 6
    current = [6]
    backtrack(3, 0):
      remaining = 0 → add [6] to result
    current.pop() → []

Result: [[2,2,2], [2,4], [3,3], [6]]

Visual Representation

Example 1: numbers = [2, 4, 6, 3], target = 6

Sorted: [2, 3, 4, 6]

Backtracking tree:
  backtrack(0, 6)
    ├─ Use 2: backtrack(0, 4)
    │   ├─ Use 2: backtrack(0, 2)
    │   │   └─ Use 2: backtrack(0, 0) → [2,2,2] ✓
    │   └─ Use 4: backtrack(2, 0) → [2,4] ✓
    ├─ Use 3: backtrack(1, 3)
    │   └─ Use 3: backtrack(1, 0) → [3,3] ✓
    └─ Use 6: backtrack(3, 0) → [6] ✓

Result: [[2,2,2], [2,4], [3,3], [6]]

Edge Cases

• No solution: Return empty array (e.g., numbers = [2], target = 1)
• Single number: Can use it multiple times if it divides target
• Target is one of numbers: Include single-element combination
• All numbers larger than target: Return empty array
• Target is 0: Return [[]] (empty combination)

Important Notes

• Can reuse numbers: Use i instead of i+1 in recursive call
• Sort first: Avoids duplicate combinations and enables optimization
• Early termination: If number > remaining, skip (since sorted)
• Unique combinations: Order doesn't matter, [2,4] same as [4,2]
• O(2^N) time: Explores all combinations in worst case

Why Backtracking Works

Key insight:

• We need to explore all possible ways to combine numbers
• Backtracking systematically explores all possibilities
• For each number, we try using it and recursively solve for remaining target
• Using i (not i+1) allows reusing the same number

Avoiding duplicates:

• By starting from index i (not i+1), we ensure:
  • We can reuse the current number
  • We don't consider previous numbers (which would create duplicates)
• Sorting ensures we process numbers in order

Related Problems

• Combination Sum II: Cannot reuse numbers
• Combination Sum III: Different constraints
• Combination Sum IV: Count combinations (DP)
• Subset Sum: Similar but different problem

Takeaways

• Backtracking explores all possible combinations
• Can reuse numbers by using i instead of i+1
• Sort first to avoid duplicates and enable optimization
• Early termination when number > remaining
• O(2^N) time in worst case
• Classic backtracking problem with many variations