[ivank]

P.P.S. последний кусочек статистики.
int[] m = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610
};
Максимальная сумма - 1233188. При этом невозможно получить 306002 различных сумм с помощью данного набора. То есть, если выбирать needed случайно, с вероятностью 1/4 твоя программа зависнет.

Код:

using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                if(corsize + m[i] == size)
                {
                    for(int j = 0; j <= p; j ++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }

                    Console.WriteLine("{0} = {1};", m[i], size);

                    return 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }                
            }

            return 1;
        }

        static void QSort(int[] ar, int size)
        {
            int left, right, ixLeft, ixRight;
            int[] borderLeft = new int[100];
            int[] borderRight = new int[100];
            int stach = 0;
            int copy;
            int x;
            Random r = new Random();
            borderLeft[0] = 0;
            borderRight[0] = size - 1;
            while(stach >= 0)
            {
                ixLeft = left = borderLeft[stach];
                ixRight = right = borderRight[stach];
                stach--;
                
                while(left < right)
                {
                    x = ar[r.Next(left, right)];
                    ixLeft = left;
                    ixRight = right;

                    while(ixLeft <= ixRight)
                    {
 
                        while(ar[ixLeft] > x)
                        {
                            ixLeft++;
                        }
                        while(ar[ixRight] < x)
                        {
                            ixRight--;
                        }
                    
                        if(ixLeft <= ixRight)
                        {
                            copy = ar[ixLeft];
                            ar[ixLeft] = ar[ixRight];
                            ar[ixRight] = copy;
                            ixLeft++;
                            ixRight--;
                        }
                    }

                    if(ixRight - left < right - ixLeft)
                    {
                        stach++;
                        borderLeft[stach] = ixLeft;
                        borderRight[stach] = right;
                        right = ixRight;
                    }
                    else
                    {
                        stach++;
                        borderLeft[stach] = left;
                        borderRight[stach] = ixRight;
                        left = ixLeft;
                    }
                }                
            }
        }

        static bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;        
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            int[] way = new int[m+1];
            for (int i = 0; i <= m; ++i)
                way[i] = 0;

            way[0] = 1;

            for (int i = 0; i < n; ++i)
                for (int j = m; j > 0; --j)
                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                        way[j] = num[i];
        
	    if (way[m] == 0)
            {
                Console.WriteLine("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
            
            return true;
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 42;
            int[] m = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
            };
            Random r = new Random();
            while (true)
            {
                int needed = r.Next(1665, 1233188);

                d1 = DateTime.Now;                
                summ2(m,l, needed);
                d2 = DateTime.Now;
                Console.WriteLine("ivank's time: {0}", d2 - d1);

                d1 = DateTime.Now;                
                summ(m,l, needed);
                d2 = DateTime.Now;
               Console.WriteLine("vlad's time: {0}", d2 - d1);
            }
        }
    }
}

Проверил. Реально задумывается гораздо чаще.