beingsde
Sign In
Back to all DSA patterns
Backtracking•Pattern: Backtracking•Medium

Combination sum — unique combinations summing to target

Problem Intuition & Objective

Find all combinations of numbers that sum to target (numbers can repeat).

Time ComplexityO(2^(target/min))
Optimal
Space ComplexityO(target/min) depth
Memory Bounds
Optimal Algorithmic Approach

DFS backtracking with remaining sum, allowing element reuse.

Core Invariants & Edge Cases

  • Backtrack with a start index; allow reuse by not incrementing start on recursion
  • Prune when current sum exceeds target
  • Sort candidates for more effective pruning
Previous ProblemSubsets — generate all subsets (power set)Next Problem Permutations of a list (with duplicates)

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.