How to get all subsets of an array?

Given an array: [dog, cat, mouse]

what is the most elegant way to create:

[,,]
[,,mouse]
[,cat,]
[,cat,mouse]
[dog,,]
[dog,,mouse]
[dog,cat,]
[dog,cat,mouse]

I need this to work for any sized array.

This is essentially a binary counter, where array indices represent bits. This presumably lets me use some bitwise operation to count, but I can't see a nice way of translating this to array indices though.

Elegant? Why not Linq it.

    public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source)
    {
        if (!source.Any())
            return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

        var element = source.Take(1);

        var haveNots = SubSetsOf(source.Skip(1));
        var haves = haveNots.Select(set => element.Concat(set));

        return haves.Concat(haveNots);
    }

 string[] source = new string[] { "dog", "cat", "mouse" };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     string[] combination = new string[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

You can use the BitArray class to easily access the bits in a number:

string[] animals = { "Dog", "Cat", "Mouse" };
List<string[]> result = new List<string[]>();
int cnt = 1 << animals.Length;
for (int i = 0; i < cnt; i++) {
   string[] item = new string[animals.Length];
   BitArray b = new BitArray(i);
   for (int j = 0; j < item.Length; j++) {
      item[j] = b[j] ? animals[j] : null;
   }
   result.Add(item);
}

static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> set)
{
    var state = new BitArray(set.Count);
    do
        yield return Enumerable.Range(0, state.Count)
                               .Select(i => state[i] ? set[i] : default(T));
    while (Increment(state));
}

static bool Increment(BitArray flags)
{
    int x = flags.Count - 1; 
    while (x >= 0 && flags[x]) flags[x--] = false ;
    if (x >= 0) flags[x] = true;
    return x >= 0;
}

Usage:

foreach(var strings in GetSubsets(new[] { "dog", "cat", "mouse" }))
    Console.WriteLine(string.Join(", ", strings.ToArray()));

Guffa's answer had the basic functionality that I was searching, however the line with

BitArray b = new BitArray(i);

did not work for me, it gave an ArgumentOutOfRangeException. Here's my slightly adjusted and working code:

string[] array = { "A", "B", "C","D" };
int count = 1 << array.Length; // 2^n

for (int i = 0; i < count; i++)
{
    string[] items = new string[array.Length];
    BitArray b = new BitArray(BitConverter.GetBytes(i));
    for (int bit = 0; bit < array.Length; bit++) {
        items[bit] = b[bit] ? array[bit] : "";
    }
    Console.WriteLine(String.Join("",items));
}