Find a subset with a target sum
Determine whether any subset of non-negative integers adds exactly to a non-negative target.
Course progress
Problem 95 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [3, 34, 4, 12, 5, 2]; target = 9
Expected output
True
What is happening?
The subset 4 and 5 adds exactly to 9, so a valid subset exists.
Solution strategy
Build the right mental model
Track reachable sums and update them downward for each number so the same array element cannot be reused.
Core concepts
dynamic programming · subset selection
Complexity
Time O(n x target), space O(target).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for subset-sum
using System;
class Program
{
static bool HasSubsetSum(int[] numbers, int target)
{
bool[] reachable = new bool[target + 1];
reachable[0] = true;
foreach (int number in numbers)
for (int sum = target; sum >= number; sum--)
reachable[sum] = reachable[sum] || reachable[sum - number];
return reachable[target];
}
static void Main()
{
Console.WriteLine(HasSubsetSum(new[] { 3, 34, 4, 12, 5, 2 }, 9));
}
}Knowledge check
Questions students often ask
What is the main idea behind find a subset with a target sum?
Track reachable sums and update them downward for each number so the same array element cannot be reused.
What is the time and space complexity of this solution?
Time O(n x target), space O(target).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.