Subset sum simple iterative implementation
Again has \$O(n*2^n)\$ complexity

This program, like the recursive solution in the previous question, has \$O(n*2^n)\$ complexity.  It is simple to see that you iterate \$2^n\$ times, and on each iteration you compute the sum in \$O(n)\$ time.

Using Gray code to achieve \$O(2^n)\$ time

The key to reducing the run time of this iterative solution is to remove the \$O(n)\$ summation loop.  You can only do this if you can compute the next sum from the previous sum in \$O(1)\$ time.  Unfortunately, between one iteration and the next, up to \$n\$ numbers might need to be added/subtracted.  For example, if you were on this bit pattern:

0 1 1 1 1 = arr[0] + arr[1] + arr[2] + arr[3]


The next bit pattern would be:

1 0 0 0 0 = arr[4]


You would need to add one number and subtract 4 numbers to get from the previous sum to the next sum.  This is where the Gray code comes in to play.  The Gray code is a numerical sequence where each number in the sequence differs from the previous by only 1 bit.  So if you counted upwards using a Gray code sequence, then the next sum can be computed from the previous sum by only adding/subtracting one number.

Luckily, it is easy to count upwards in a Gray code sequence.  You can just count upwards in the normal way and then convert your normal number to the corresponding Gray code number using the formula:

grayCode = n ^ (n &gt;&gt; 1)


Then to find the bit that changed, you can xor the new gray number with the previous one:

bitChanged = oldGray ^ newGray;


One tricky part is that you need to know the bit number of the bit that changed.  Normally, I would do:

bitIndex = 31 - CLZ(bitChanged);


where CLZ() is a builtin "count leading zeros" function.  I couldn't find a builtin function in C# for that though, so I wrote my own.  There are fast versions of CLZ() that can be done in constant time using a lookup table, but I decided to use a looping version.  In the case of counting upwards using Gray numbers, bitChanged will be 0x1 50% of the time, 0x2 25% of the time, 0x4 12.5% of the time, etc.  Because of this, the looping variant will take amortized constant time since it operates faster on smaller bit numbers.

Sample Gray code implementation

I took your program and changed two functions: FindSubsetSum() and PrintSubset().  I also added my own clz() function.  Here is the modified parts of your code:

    private static void FindSubsetSum(int[] arr, int targetSum)
    {
        int length     = arr.Length;
        int iEnd       = 1 &lt;&lt; length;
        int currentSum = 0;
        int oldGray    = 0;

        for (int i = 1; i &lt; iEnd; i++)
        {
            int newGray    = i ^ (i &gt;&gt; 1);
            int bitChanged = oldGray ^ newGray;
            int bitNumber  = 31 - clz(bitChanged);

            if ((newGray &amp; bitChanged) != 0)
            {
                // Bit turned to 1 = Add element.
                currentSum += arr[bitNumber];
            }
            else
            {
                // Bit turned to 0 = Subtract element.
                currentSum -= arr[bitNumber];
            }
            // Check for sum and print if equal
            if (currentSum == targetSum)
            {
                PrintSubSet(arr, newGray);
            }
            oldGray = newGray;
        }
    }

    private static void PrintSubSet(int[] arr, int bits)
    {
        Console.Write("(");
        for (int i = 0; i &lt; arr.Length; i++)
        {
            if ((bits &amp; (1 &lt;&lt; i)) != 0)
            {
                Console.Write(arr[i]);

                if (i &lt; arr.Length - 1)
                {
                    Console.Write(" ,");
                }
            }
        }
        Console.WriteLine(")");
    }

    // This can be replaced with a better variant, but this variant
    // will do the job for the Gray code sequence since the low
    // bit numbers will appear the vast majority of the time.
    private static int clz(int x)
    {
        int lz = 32;

        while (x != 0) {
            x &gt;&gt;= 1;
            lz--;
        }
        return lz;
    }