Subset Sum (Bitmask)

README.txt

This problem was asked by Google.

Given a list of integers S and a target number k, 
write a function that returns a subset of S that adds up to k.
If such a subset cannot be made, then return null.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since it sums up to 24.

Program.cs

class Program
{
    static void Main(string[] args)
    {
        int k = 24;
        int[] s = new int[] { 12, 1, 61, 5, 9, 2 };
        s = s.Where(x => x <= k).ToArray();

        int n = s.Length;
        List<int> indices = new List<int>();
        for (int i = 1; i < 1 << n; i++)
        {
            long sum = 0L;
            for (int j = 0; j < n; j++)
            {
                if ((i & (1 << j)) != 0)
                {
                    sum += s[j];
                    indices.Add(j);
                }
            }
            if (sum == k)
            {
                Console.WriteLine(string.Join(", ", indices.Select(x=>s[x])));
            }
            indices.Clear();
        }
    }
}