How can I determine if a certain number can be made up from a set of numbers?

Question

So I have an integer, e.g. 1234567890, and a given set of numbers, e.g. {4, 7, 18, 32, 57, 68}

The question is whether 1234567890 can be made up from the numbers given (you can use a number more than once, and you don't have to use all of them). In the case above, one solution is:
38580246 * 32 + 1 * 18

(Doesn't need to give specific solution, only if it can be done)

My idea would be to try all solutions. For example I would try
1 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 4
2 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 8
3 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 12
.....
308 641 972 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567888
308 641 973 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567892 ==> exceeds
0 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 7
1 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 11
2 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 15
and so on...

Here is my code in c#:

    static int toCreate = 1234567890;
    static int[] numbers = new int[6] { 4, 7, 18, 32, 57, 68};
    static int[] multiplier;
    static bool createable = false;

    static void Main(string[] args)
    {
        multiplier = new int[numbers.Length];
        for (int i = 0; i < multiplier.Length; i++)
            multiplier[i] = 0;

        if (Solve())
        {
            Console.WriteLine(1);
        }
        else
        {
            Console.WriteLine(0);
        }
    }

    static bool Solve()
    {
        int lastIndex = 0;
        while (true)
        {
            int comp = compare(multiplier);
            if (comp == 0)
            {
                return true;
            }
            else if (comp < 0)
            {
                lastIndex = 0;
                multiplier[multiplier.Length - 1]++;
            }
            else
            {
                lastIndex++;
                for (int i = 0; i < lastIndex; i++)
                {
                    multiplier[multiplier.Length - 1 - i] = 0;
                }
                if (lastIndex >= multiplier.Length)
                {
                    return false;
                }
                multiplier[multiplier.Length - 1 - lastIndex]++;
            }
        }
    }

    static int compare(int[] multi)
    {
        int osszeg = 0;
        for (int i = 0; i < multi.Length; i++)
        {
            osszeg += multi[i] * numbers[i];
        }
        if (osszeg == toCreate)
        {
            return 0;
        }
        else if (osszeg < toCreate)
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }

The code works fine (as far as I know) but is way too slow. It takes about 3 secs to solve the example, and there may be 10000 numbers to make from 100 numbers.

Missy

Am i correct assuming that numbers in a set are coprime to each other? – Timer

It seems to me you could eliminate quite a lot of the potential answers by doing some basic math upfront for each number. You know for example that when you are only adding one number you only have to check to see if the desired number is divisible by that number. That is one check rather than iterating over every possible number until exceeding the desired number – Steapsin

The modulus operator might be your friend here. You could start off by doing 1234567890 % 68, then see if you can create the remainder out of your other smaller numbers. That would turn it into a smaller problem first. – Clam

@TrentSartain That is a clearer example of what I was trying to say – Steapsin

If the code works fine, is it not better to have on CodeReview? – Proton

@TrentSartain Actually as I think further about this problem, modulus won't be that helpful. It will do a good job at finding the solution in certain cases, but won't guarantee that a solution doesn't exist. For example take target number of 28 and given numbers of 5 and 9. It will do 28 % 5 = 3 => 3 % 9 = 3 and 28 % 9 = 2 => 2 % 5 = 2 and conclude that it can't be done, but in reality (2 * 5) + (2 * 9) = 28 so it can be done – Steapsin

@KevinWells Ah! True enough. Perhaps it can be used as more of a heuristic... I'm working on a solution now. I'll post it as an answer when I'm done. – Clam

@KevinWells I added my solution. Explanation to follow. – Clam

It's not clear to me from your problem description what operations you're allowed to perform on the numbers. At first I thought you were asking how to solve the countdown numbers game, but it sounds like you actually want a program to find out if the target can be formed as a linear combination of the other numbers? Do the coefficients in that linear combination have to be positive? I'm unclear on the rules, here. – Snow

Answer 1

I have a recursive solution. It solves the OP's original problem in about .005 seconds (on my machine) and tells you the calculations.

private static readonly int Target = 1234567890;
private static readonly List<int> Parts = new List<int> { 4, 7, 18, 32, 57, 68 };

static void Main(string[] args)
{
    Console.WriteLine(Solve(Target, Parts));
    Console.ReadLine();
}

private static bool Solve(int target, List<int> parts)
{
    parts.RemoveAll(x => x > target || x <= 0);
    if (parts.Count == 0) return false;

    var divisor = parts.First();
    var quotient = target / divisor;
    var modulus = target % divisor;

    if (modulus == 0)
    {
        Console.WriteLine("{0} X {1}", quotient, divisor);
        return true;
    }

    if (quotient == 0 || parts.Count == 1) return false;

    while (!Solve(target - divisor * quotient, parts.Skip(1).ToList()))
    {
        if (--quotient != 0) continue;
        return Solve(target, parts.Skip(1).ToList());
    }

    Console.WriteLine("{0} X {1}", quotient, divisor);
    return true;
}

Basically, it goes through each number to see if there is a possible solution "below" it given the current quotient and number. If there isn't, it subtracts 1 from the quotient and tries again. It does this until it exhausts all options for that number and then moves on to the next number if available. If all numbers are exhausted, there is no solution.

Clam

This is stunningly fast, but there is unfortunately at least one bug. The line where you say if (quotient == 0) return false; should not be there since that would imply that for a target of 5 and parts { 10, 5 } there is no solution when there clearly is (you can just use 0 10's). I'm checking the program more thoroughly and will let you know if I run into anything else – Steapsin

Well you beat me to a good answer. I can't see any edge cases where this either doesn't work (except the aforementioned case you can filter out easily) or works very slowly, so this seems like the best answer – Steapsin

In fact the fix is as easy as adding Parts.RemoveAll(x => x > Target); near the beginning of Main – Steapsin

@KevinWells Excellent catch! I updated the solution. – Clam

Answer 2

Don't have the means test the solution, but the following should do.

Given a target number target and a set numbers of valid numbers:

bool FindDecomposition(int target, IEnumerable<int> numbers, Queue<int> decomposition)
{
    foreach (var i in numbers)
    {
        var remainder = target % i;

        if (remainder == 0)
        {
             decomposition.Enqueue(i);
             return true;
        } 

        if (FindDecomposition(remainder, numbers.Where(n => n < i), decomposition))
        {
             return true;
        }
    }

    return false
}

Building up n from decomposition is pretty straightforward.

Cholera

This doesn't work for the same reason the last wrong answer doesn't work (though I'm making some assumptions since you aren't saying very clearly what this is doing). If you are just doing desiredNumber % numberFromList for each given number then check what happens when you try to do that for desired number 28 and given numbers 5 and 9. It will do 28 % 5 = 3 => 3 % 9 = 3 and 28 % 9 = 2 => 2 % 5 = 2 and conclude that it can't be done, but in reality (2 * 5) + (2 * 9) = 28 so it can be done. – Steapsin

@KevinWells Very true! I missed the previous answer, it has been deleted. I'll leave this one so nobody else makes the same mistake. – Cholera

Cool, I also left a comment on the question explaining why this approach won't work. I initially gravitated to the same thing until I found a counter-example – Steapsin

Answer 3

You could always try using the modulo function in conjunction with LINQ expressions to solve the problem.

You would have a list and a running modulo variable to keep track of where you are at in your iteration. Then simply use recursion to determine whether or not you have meet the conditions.

One example would be the following:

static int toCreate = 1234567890;
    static List<int> numbers = new List<int> { 4, 7 };


    static void Main(string[] args)
    {
        numbers.Sort();
        numbers.Reverse();

        Console.WriteLine(Solve(numbers,toCreate).ToString());
    }

    static bool Solve(List<int> lst1, int runningModulo)
    {
        if (lst1.Count == 0 && runningModulo != 0) 
            return false;
        if (lst1.Count == 0 || runningModulo == 0)
            return true;

        return numbers.Any(o => o < (toCreate % lst1.First())) ? //Are there any in the remaining list that are smaller in value than the runningModulo mod the first element in the list.
            Solve(lst1.Where(o => o != lst1.First()).ToList(), runningModulo % lst1.First()) //If yes, then remove the first element and set the running modulo = to your new modulo
            : Solve(lst1.Where(o => o != lst1.First()).ToList(), toCreate); //Otherwise, set the running modulo back to the original toCreate value.
    }

Isostasy

This doesn't work for the same reason the last wrong answer doesn't work. If you are just doing desiredNumber % numberFromList for each given number then check what happens when you try to do that for desired number 28 and given numbers 5 and 9. It will do 28 % 5 = 3 => 3 % 9 = 3 and 28 % 9 = 2 => 2 % 5 = 2 and conclude that it can't be done, but in reality (2 * 5) + (2 * 9) = 28 so it can be done – Steapsin