Another Casual Coder

The problem in this post is related to subsets, and the solution shows a nice trick to avoid mystical recursive solutions. The enumeration for the problem is simple: given a set S of numbers (integers) and a target number N, print all the subsets S' of S such that Summation(S') = N.
The trick to generate the subsets lies in the binary representation of a number. Suppose that we want to generate all the subsets of a set with 3 elements. We know from basic set theory that the number of subsets of this set is 2^3, also known as 8. Now let's see the binary representation of all the numbers from 0 to 7:

0 = 0 0 0
1 = 0 0 1
2 = 0 1 0
3 = 0 1 1
4 = 1 0 0
5 = 1 0 1
6 = 1 1 0
7 = 1 1 1

The bits interpretation here should be: "if the bit is 1, then the element at that position belongs to the subset". Hence take for instance the number 3:

3 = 0 1 1

Since our original set has 3 elements, say {a,b,c}, this third subset should contain only elements b and c since their respective bits are 1.

Hence in other words, to generate the subsets of a set, the high-level algorithm should be:

For all numbers k from 0 to (2^len(set)) - 1
For all the bits i of k
if i is 1, add the corresponding element to the subset

Exponential in time, but avoids the overhead of recursive calls. Here is the code showing how to do this for the original problem posted:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SubSetAddingToNumberNamespace
{
class Program
{
static void Main(string[] args)
{
int[] set = { 1, 7, -3, 9, 6, -8, 12, 11, 5, -4, 2, 17 };
int target = 67;
SubSetAddingToNumber(set, target);
}
static void SubSetAddingToNumber(int[] set,
int target)
{
if (set == null)
{
return;
}
int powerSetCardinality = (int)Math.Pow(2, set.Length);
for (int i = 0; i < powerSetCardinality; i++)
{
int n = i;
int partialSum = 0;
LinkedList<int> subSet = new LinkedList<int>();
int index = 0;
while (n > 0)
{
if (n % 2 == 1)
{
subSet.AddLast(set[index]);
partialSum += set[index];
}
n /= 2;
index++;
}
if (partialSum == target)
{
int count = 0;
foreach (int item in subSet)
{
if (item < 0)
{
Console.Write("({0})", item);
}
else
{
Console.Write(item);
}
if (count < subSet.Count - 1)
{
Console.Write("+");
}
count++;
}
Console.WriteLine("={0}", target);
}
}
}
}
}
With this output:

7+たす9+たす6+たす12+たす11+たす5+たす17=わ67
1+7+(-3)+9+たす6+たす12+たす11+たす5+たす2+たす17=わ67