Sum to Target - Sam Ngo

Overview

Excel Formulas Algorithms Dynamic Arrays

The Subset Sum Problem is a classic computer science challenge: given a list of numbers and a target, find all subsets that sum exactly to the target. This workbook solves it entirely with Excel formulas — no VBA required. It demonstrates three approaches of increasing sophistication, from a step-by-step breakdown to a single-cell formula.

Download the Excel file (.xlsx)

Three Approaches

Sheet 1: Step-by-Step Breakdown

Uses DEC2BIN + SEQUENCE to generate all 2ⁿ-1 binary combinations

Each binary string represents a subset (1 = include, 0 = exclude). The formula extracts individual digits with MID, multiplies by the number list using MMULT, and filters for subsets matching the target.

Sheet 2: Single Formula (275 characters)

The entire algorithm condensed into one cell using FILTER, BASE, and SEQUENCE

Replaces DEC2BIN with BASE to handle larger number lists, and combines all steps into a single dynamic array formula that spills the results.

Sheet 3: LET Formula (444 characters)

Readable version using LET for named intermediate variables

The same algorithm wrapped in LET with descriptive variable names, making the logic auditable and maintainable. Outputs all matching subsets showing which numbers are included.

Key Formula Techniques

Binary Enumeration: SEQUENCE(2^n-1) generates all possible subset indices; BASE() or DEC2BIN() converts to binary inclusion masks.
MMULT for Dot Product: Multiplies the binary mask by the number list to compute each subset's sum in one operation.
FILTER for Results: Filters the binary masks to only those whose dot product equals the target.

When to Use This

This pattern solves real business problems: reconciling invoices that should sum to a specific payment, finding combinations of line items that match a budget allocation, or identifying which transactions compose a bank statement total. It's also an excellent demonstration of Excel's dynamic array capabilities for algorithm implementation.