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.

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.