Verify if a list (or a sublist of that list) of decimal values can equal a certain sum

Question

Hi I have a List<decimal> containing values between ]0;1]. I want to check if a total (or subtotal) of these values can equal 1 (or almost).

I can also use Linq functions to filter or manipulate the list.

Desired results:

• A list containing {0.7, 0.7, 0.7} should return false;
• A list containing {0.7, 0.3, 0.7} should return true;
• A list containing {0.777777, 0.2, 0.1} should return false;
• A list containing {0.33333, 0.33333, 0.33333} should return true;
• A list containing {0.4, 0.5, 0.6, 0.3} should return true.

Obviously, I'll want something with the lowest performance cost possible.

Answer 1

UPDATED -- now doesn't repetively sum try this

bool isClose(IEnumerable<decimal> list, decimal epislon) {
  return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon);
}
// Define other methods and classes here
bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) {
  if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true;
  if (leftSum>1+epsilon) return false;
  if (leftSum+right.Sum()< 1-epsilon) return false;
  if (!right.Any()) return false;

  for (var i=0;i<right.Count();i++) {
    var skip=right.Skip(i);
    var newItem=skip.First();
    if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true;
  }
  return false;
}



isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false
isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true
isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false
isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true

EDIT 5th Test

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true

Answer 2

This is the subset sum problem, a special case of the knapsack problem. It's hard (NP-complete). The best known algorithms have exponential complexity. However there are approximate algorithms with polynomial complexity. These answer the question 'is there a subset that sums to 1±ε ?'

• http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
• http://en.wikipedia.org/wiki/Subset_sum_problem
• Knuth's TAOCP (probably)

Answer 3

Here is a rather straightforward, niave, brute force approach. It won't be efficient, but hopefully it's easier to understand.

private const decimal threshold = .001M;

public static bool CloseEnough(decimal first, decimal second, decimal threshold)
{
    return Math.Abs(first - second) < threshold;
}

private static bool SubsetSum(List<decimal> data, int desiredSum)
{

    int numIteratons = (int)Math.Pow(2, data.Count);

    for (int i = 1; i < numIteratons; i++)
    {
        decimal sum = 0;
        int mask = 1;
        for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++)
        {
            if ((i & mask) > 0)
            {
                sum += data[j];
            }
            mask <<= 1;
        }

        if (CloseEnough(sum, desiredSum, threshold))
        {
            return true;
        }
    }

    return false;
}