Infinity loop in sum combination

Question

I have the following code to search combinations that fit a gave sum. But the problem is with low decimal numbers.

Like, when I try to fit the sum 11.90 with 3.15 and 0.40 the program starts a infinit loop. When I try with 3.15 and 2.45 I recieve the following result (3.15 | 3.15 | 3.15 | 2.45) that is correct.

public static void findNumbers(List<double> ar, double sum, List<List<double>> res, List<double> r, int i)
{   
    // If current sum becomes negative 
    if (sum < 0)
    {
        return;
    }
    // if we get exact answer 
    if (sum < 2)
    {
        res.Add(r);
        return;
    }

    // Recur for all remaining elements that 
    // have value smaller than sum. 

    while (i < ar.Count() && sum - ar[i] >= 0)
    {
        // Till every element in the array starting 
        // from i which can contribute to the sum 
        r.Add(ar[i]); // Add them to list
        // recur for next numbers                 
        findNumbers(ar, sum - ar[i], res, r, i);
        i++;

        r.RemoveAt(r.Count() - 1);
    }
}

I'ld know how to take out this loop.

Answer 1

Your code has imho 2 discussable points

if (sum < 2)

Shouldn't you look for a exact sum? e.g. sum == 0 or better Math.Abs(sum) < tolerance (like 0.0005) since you are working with doubles.

res.Add(r);

With res.Add(r) you are adding a reference to r. But then with r.RemoveAt(r.Count() - 1); your referenced r in the res list will also be influenced. So I would suggest to add a copy of r to res:

res.Add(r.GetRange(0, r.Count));

EDIT:

See a working sample at https://github.com/hcetinkaya/Combinations.git

Your sample with sum = 11.90 and array of 3.15 and 0.4 and tolerance 2.0 => 9.90 <= sum <= 11.90, yields following results:

(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 3,15, 3,15, 3,15)