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; i < 1000; i++) ns.Add(1);
var s1 = Stopwatch.StartNew();
bool result = SubsetSum(ns, 1000);
s1.Stop();
Console.WriteLine(result);
Console.WriteLine(s1.Elapsed);
Console.Read();
}
static bool SubsetSum(ist<int> nums, int targetL)
{
var left = new List<int> { 0 };
var right = new List<int> { 0 };
foreach (var n in nums)
{
if (left.Count < right.Count) left = Insert(n, left);
else right = Insert(n, right);
}
int lefti = 0, righti = right.Count - 1;
while (lefti < left.Count && righti >= 0)
{
int s = left[lefti] + right[righti];
if (s < target) lefti++;
else if (s > target) righti--;
else return true;
}
return false;
}
static List<int> Insert(int num, List<int> nums)
{
var result = new List<int>();
int lefti = 0, left = nums[0]+num;
for (var righti = 0; righti < nums.Count; righti++)
{
int right = nums[righti];
while (left < right)
{
result.Add(left);
left = nums[++lefti] + num;
}
if (right != left) result.Add(right);
}
while (lefti < nums.Count) result.Add(nums[lefti++] + num);
return result;
}
}
}
And here is an improved version that prunes the sets:
static bool SubsetSum(List<int> nums, int target)
{
var remainingSum = nums.Sum();
var left = new List<int> { 0 };
var right = new List<int> { 0 };
foreach (var n in nums)
{
if (left.Count == 0 || right.Count == 0) return false;
remainingSum -= n;
if (left.Count < right.Count) left = Insert(n, left, target - remainingSum - right.Last(), target);
else right = Insert(n, right, target - remainingSum - left.Last(), target);
}
int lefti = 0, righti = right.Count - 1;
while (lefti < left.Count && righti >= 0)
{
int s = left[lefti] + right[righti];
if (s < target) lefti++;
else if (s > target) righti--;
else return true;
}
return false;
}
static List<int> Insert(int num, List<int> nums, int min, int max)
{
var result = new List<int>();
int lefti = 0, left = nums[0]+num;
for (var righti = 0; righti < nums.Count; righti++)
{
int right = nums[righti];
while (left < right)
{
if (min <= left && left <= max) result.Add(left);
left = nums[++lefti] + num;
}
if (right != left && min <= right && right <= max) result.Add(right);
}
while (lefti < nums.Count)
{
left = nums[lefti++] + num;
if (min <= left && left <= max) result.Add(left);
}
return result;
}
This last one solved the problem with 100000 ones in about 5 milliseconds (but this is a best case of the algorithm, with real world data it will be slower).
For your use this algorithm is probably fast enough (and I don’t see any obvious improvements). If you enter 10,000 products with a random price between 0 and 20 and your goal is to sum to 500 this is solved in 0.04 seconds on my laptop.
Edit: I just read on Wikipedia that the best known algorithm is O(2^(n/2)*n)
. This one is O(2^(n/2))
. Do I get the Turing Award?