Subset sum problem
Here is my algorithm. It runs in O(2^(n/2)) and solves SubsetSum(1000, list-of-1000-ones) in 20 milliseconds. See the comments at the end of IVlad’s post. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace SubsetSum { class Program { static void Main(string[] args) { var ns = new List<int>(); for (int i = 0; … Read more