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:
Let us try our method with the examples above:
Remark: I’m using the Polyglot Notebook feature in VS Code. Love it!