Subset sum simple iterative implementation

Question

Here is the simplest iterative implementation of Subset sum problem that I could come up with¹, as a follow up to this recursive implementation of the same problem:

using System;
using System.Linq;

namespace Exercise
{
class SubsetSumBinaryNumber
{
    static void Main(string[] args)
    {
        int[] arr = { 2, 3, 1, -1 };
        PrintSet(arr, "Initial Set:");

        int wantedSum = 4;
        Console.WriteLine("Wanted sum = {0}", wantedSum);

        FindSubsetSum(arr, wantedSum);
    }
    //-----------------------------------------------------------------------                      
    /* Method: FindSubsetSum(int[] arr, int sum) */
    private static void FindSubsetSum(int[] arr, int targetSum)
    {
        // convert to base 
        int toBase = 2;
        // length of binary number
        int length = arr.Length;
        // max value of binary number with "arr.Length" digits
        int iEnd = (int) Math.Pow(length, 2); 

        for (int number = 0; number < iEnd; number++)
        {
            // convert current number to binary array
            bool[] binaryNumber = Enumerable.Range(1, length).Select(i => number / (1 << (length - i)) % 2 == 1).ToArray();

            // sum all elements with "true" indexes
            int currentSum = 0;
            for (int j = 0; j < binaryNumber.Length; j++)
            {
                if(binaryNumber[j] == true)
                {
                    currentSum += arr[j];
                }       
            }

            // check for sum and print if equal
            if (currentSum == targetSum)
            {
                PrintSubSet(arr, binaryNumber);
            }
        }
    }
}
}

Input:

-

Output:

Initial Set.
{2 ,3 ,1 ,-1}
Wanted sum = 4
(1 ,3,)
(-1 ,3 ,2)

The algorithm is based on viewing all the combination of indexes of the initial set as a binary number (0's and 1's), then in order to go through all the combinations we simply increment through all the consecutive binary values from 0 to 2^{set cardinality} and sum the set elements that match the 1's in the binary value, check the sum and print them if sum matches the wanted value.

Could the for loop be reduced in half if both current binary and its complement are checked simultaneously?

What is the complexity of this algorithm?

Any remarks regarding style and optimization will be appreciated.

---

Helper functions:

    /* Method: PrintSubSet(int[] arr, bool[] subSet) */
    private static void PrintSubSet(int[] arr, bool[] subSet)
    {
        Console.Write("(");
        for (int i = 0; i < arr.Length; i++)
        {
            if (subSet[i] == true)
            {
                Console.Write(arr[i]);

                if (i < arr.Length - 1)
                {
                    Console.Write(" ,");
                }
            }
        }
        Console.WriteLine(")");
    }
    //----------------------------------------------------------------------
    /* Method: PrintSet(int[] arr, string label = "") */
    private static void PrintSet(int[] arr, string label = "")
    {
        Console.WriteLine(label);

        Console.Write("{");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);

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

---

^{1. The most of the algorithms (that I could find) use recursion, dynamic programming and other fairly complex iterative approaches.}

Answer 1

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 >> 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 << length;
        int currentSum = 0;
        int oldGray    = 0;

        for (int i = 1; i < iEnd; i++)
        {
            int newGray    = i ^ (i >> 1);
            int bitChanged = oldGray ^ newGray;
            int bitNumber  = 31 - clz(bitChanged);

            if ((newGray & 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 < arr.Length; i++)
        {
            if ((bits & (1 << i)) != 0)
            {
                Console.Write(arr[i]);

                if (i < 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 >>= 1;
            lz--;
        }
        return lz;
    }

Answer 2

i don't know much but i found problem in your code and it is pow(2, length) which is number of subset of any set.

and thank you i have been looking for iterative approach for long time.