Subset Sums

using System;
//You are given a list of N numbers. Write a program that counts all non-empty subsets from this list, which have sum of their elements exactly S.
//Example: if you have a list with 4 elements: { 1, 2, 3, 4 } and you are searching the number of non-empty subsets which sum is 4, the answer will
//be 2. The subsets are: { 1, 3 } and { 4 }.
//Input
//The input data is being read from the console.
//On the first input line there will be the number S.
//On the second line you must read the number N.
//On each of the following N lines there will be one integer number written – all the numbers from the list.
//The input data will always be valid and in the format described. There is no need to check it explicitly.
//Output
//The output must be printed on the console.
//On the only output line you must print the number of the non-empty subsets, which have sum of all its elements exactly S.


class Program
{
    static void Main()
    {
        long s = long.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        long[] num = new long[n];

        for (int i = 0; i < n; i++)
        {
            num[i] = long.Parse(Console.ReadLine());
        }

        long sum = 0;
        int answer = 0;
        for (int i = 1; i < Math.Pow(2, n); i++)
        {
            for (int j = 0; j < num.Length; j++)
            {
                if ((i >> j & 1) == 1)
                {
                    sum += num[j];
                }
            }
            if (sum == s)
            {
                answer++;
            }
            sum=0;
        }
        Console.WriteLine(answer);
    }
}