Skip to main content

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:

Let us try our method with the examples above:

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

Popular posts from this blog

DevToys–A swiss army knife for developers

As a developer there are a lot of small tasks you need to do as part of your coding, debugging and testing activities.  DevToys is an offline windows app that tries to help you with these tasks. Instead of using different websites you get a fully offline experience offering help for a large list of tasks. Many tools are available. Here is the current list: Converters JSON <> YAML Timestamp Number Base Cron Parser Encoders / Decoders HTML URL Base64 Text & Image GZip JWT Decoder Formatters JSON SQL XML Generators Hash (MD5, SHA1, SHA256, SHA512) UUID 1 and 4 Lorem Ipsum Checksum Text Escape / Unescape Inspector & Case Converter Regex Tester Text Comparer XML Validator Markdown Preview Graphic Color B

Help! I accidently enabled HSTS–on localhost

I ran into an issue after accidently enabling HSTS for a website on localhost. This was not an issue for the original website that was running in IIS and had a certificate configured. But when I tried to run an Angular app a little bit later on http://localhost:4200 the browser redirected me immediately to https://localhost . Whoops! That was not what I wanted in this case. To fix it, you need to go the network settings of your browser, there are available at: chrome://net-internals/#hsts edge://net-internals/#hsts brave://net-internals/#hsts Enter ‘localhost’ in the domain textbox under the Delete domain security policies section and hit Delete . That should do the trick…

Azure DevOps/ GitHub emoji

I’m really bad at remembering emoji’s. So here is cheat sheet with all emoji’s that can be used in tools that support the github emoji markdown markup: All credits go to rcaviers who created this list.