算法问题

Question

任给1<=n<=20个不同等非零正整数，每个正整数最多使用一次，请问这n个正整数能够加和的结果共有多少种？
这个是我们学校软件技能大赛的题目，大家讨论下啊
用C#写下啊、。。呵呵

Answer 1

    static void Main(string[] args)
    {
        int i = GetCombinationCount(new int[] { 1, 2, 3 });   //i=6
    }    static int GetCombinationCount(int[] nums)
    {
        Dictionary<int, int> sums = new Dictionary<int, int>();
        int combinations = 1 << nums.Length;        for (int i = 1; i < combinations; i++)
        {
            string masks = Convert.ToString(i, 2).PadLeft(nums.Length, '0');
            int sum = 0;
            for (int j = 0; j < masks.Length; j++)
            {
                if (masks[j] == '1') sum += nums[j];
            }
            sums[sum] = 1;
        }
        return sums.Count;
    }
}

Answer 2

这样写可能更能对一些算法派的胃口：
原理简单的说就是n个灯(或n bits)，用或者不用，总的组合等于2^nstatic int GetCombinationCount(int[] nums)
{
    Dictionary<int, int> sums = new Dictionary<int, int>();
    int combinations = 1 << nums.Length;    for (int i = 1; i < combinations; i++)
    {
        int sum = 0, mask = i;
        foreach (int n in nums)
        {
            if (mask == 0) break;
            if (mask % 2 == 1) sum += n;
            mask >>= 1;
        }
        sums[sum] = 1;
    }
    return sums.Count;
}

Answer 3

"任给1 <=n <=20个不同等非零正整数"这句没懂！
假如n＝4，这四个数是1，2，3，4呢，还是1000，786，33，223？

Answer 4

应该有2的n次方-1种：        static void Main(string[] args)
        {
            int[] a = { 24, 4, 31, 14, 59 };
            GetCombination(a);
        }
        static string GetBinaryString(int n, int length)
        {
            string result = string.Empty;
            int mod = 0;
            while (n != 0)
            {
                mod = n % 2;
                n = n / 2;
                result = mod.ToString() + result;
            }
            if (result.Length < length)
                result = result.PadLeft(length, '0');
            return result;
        }        static void GetCombination(int[] nums)
        {
            double count = Math.Pow(2, nums.Length);
            for (int i = 1; i <= count - 1; i++)
            {
                Console.Write("可能的组合有:");
                string str = GetBinaryString(i, nums.Length);
                int sum = 0;
                for (int j = 0; j < str.Length; j++)
                {
                    if (str[j] == '1')
                    {
                        Console.Write(nums[j] + " ");
                        sum += nums[j];
                    }
                }
                Console.WriteLine("和为:" + sum);
            }
        }输出为：
=======================================================
可能的组合有:59 和为:59
可能的组合有:14 和为:14
可能的组合有:14 59 和为:73
可能的组合有:31 和为:31
可能的组合有:31 59 和为:90
可能的组合有:31 14 和为:45
可能的组合有:31 14 59 和为:104
可能的组合有:4 和为:4
可能的组合有:4 59 和为:63
可能的组合有:4 14 和为:18
可能的组合有:4 14 59 和为:77
可能的组合有:4 31 和为:35
可能的组合有:4 31 59 和为:94
可能的组合有:4 31 14 和为:49
可能的组合有:4 31 14 59 和为:108
可能的组合有:24 和为:24
可能的组合有:24 59 和为:83
可能的组合有:24 14 和为:38
可能的组合有:24 14 59 和为:97
可能的组合有:24 31 和为:55
可能的组合有:24 31 59 和为:114
可能的组合有:24 31 14 和为:69
可能的组合有:24 31 14 59 和为:128
可能的组合有:24 4 和为:28
可能的组合有:24 4 59 和为:87
可能的组合有:24 4 14 和为:42
可能的组合有:24 4 14 59 和为:101
可能的组合有:24 4 31 和为:59
可能的组合有:24 4 31 59 和为:118
可能的组合有:24 4 31 14 和为:73
可能的组合有:24 4 31 14 59 和为:132
请按任意键继续. . .

Answer 5

几个数和值和另外的几个数一样的情况还要减去。
gomoku写得很好了
用dictionary 
其中的sums[sum] = 1 这句话很好很强大