Find a subset from a set of values whose sum is closest to a specific value–C#

I got an interesting question from my girlfriend last week:

Given I have a list of numbers, I want to select a subset of numbers that added up matches closest to a specific (positive) value.

Let me give a simplified example to explain what she was asking for:

If our list is [12, 79, 99, 91, 81, 47] and the expected value is 150, it should return [12, 91, 47] as 12+91+47 is 150.

If our list is [15, 79, 99, 6, 69, 82, 32] and the expected value is 150 it should return [69, 82] as 69+82 is 151, and there is no subset whose sum is 150.

This turns out to be known as the Subset sum problem and is a computational hard problem to solve. Luckily the list of numbers she needs to work with is quite small (about 50 numbers) and we can easily brute force this.

Yesterday I explained how this problem can be solved in Excel, but what is the fun in that?! Let us have a look on how we can do this in C#.

With some help of Github Copilot I came up with the following solution:

	public static List<int> SubsetSum(int[] arr, int target)
	{
	int n = arr.Length;
	// Initialize a 2D array
	int[,] dp = new int[n + 1, target + 1];
	// Fill the 2D array
	for (int i = 1; i <= n; i++)
	{
	for (int j = 1; j <= target; j++)
	{
	// If the current element is less than or equal to the target
	if (arr[i - 1] <= j)
	// Choose the maximum between the current dp value and the dp value of the remaining target after subtracting the current element
	dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - arr[i - 1]] + arr[i - 1]);
	else
	// If the current element is greater than the target, use the dp value of the previous element
	dp[i, j] = dp[i - 1, j];
	}
	}
	List<int> subset = new ();
	int x = n, y = target;
	// Trace back the dp table to find the subset
	while (x > 0 && y > 0)
	{
	// If the current dp value is different from the previous dp value, add the current element to the subset
	if (dp[x, y] != dp[x - 1, y])
	{
	subset.Add(arr[x - 1]);
	y -= arr[x - 1];
	}
	x--;
	}
	// Return the subset
	return subset;
	}

view raw SubsetSum.cs hosted with ❤ by GitHub

Let us try our method with the examples above:

Remark: I’m using the Polyglot Notebook feature in VS Code. Love it!