Problem 12. * Zero Subset

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;

namespace _12.ZeroSubset
{
    class ZeroSubset
    {
        static void Main(string[] args)
        {
            //int[] numbers = { 3, -2, 1, 1, 8 };
            //int[] numbers = { 3, 1, -7, 35, 22 };
            //int[] numbers = { 1, 3, -4, -2, -1 };
            int[] numbers = { 1, 1, 1, -1, -1 };
            //int[] numbers = { 0, 0, 0, 0, 0 };


            //TRIVIAL CASE - ALL ZEROS
            int countZeros = 0;
            for (int i = 0; i < numbers.Length; i++)
            {
                if (numbers[i] == 0)
                {
                    countZeros++;
                }
            }
            if(numbers.Length == countZeros)
            {
                for (int i = 0; i < numbers.Length; i++)
                {
                    if (i < numbers.Length - 1)
                    {
                        Console.Write("0 + ");
                    }
                    else
                    {
                        Console.WriteLine("0 = 0");
                    }
                }
                return;
            }

            //ALL OTHER CASES
            int coefficientCombinations = (int) Math.Pow(2, numbers.Length) - 1;
            for (int coefficients = coefficientCombinations; coefficients > 0; coefficients--)
            {
                if(onlyOneBitSet(coefficients))
                {
                    continue;
                }
                int sum = 0;
                int sequenceMembersCount = 0;
                for (int index = 0; index < numbers.Length; index++)
                {
                    int bitIndex = (numbers.Length - 1) - index;
                    int numberIndex = index;
                    int coefficient = getBit(coefficients, bitIndex);
                    sum += coefficient * numbers[numberIndex];
                    if(coefficient == 1)
                    {
                        sequenceMembersCount++;
                    }
                }
                int sequenceMembersCountSaved = sequenceMembersCount;
                if (sum == 0)
                {
                    for (int i = 0; i < numbers.Length; i++)
                    {
                        int bitIndex = (numbers.Length - 1) - i;
                        int numberIndex = i;
                        int coefficient = getBit(coefficients, bitIndex);
                        if (coefficient == 1 && sequenceMembersCount == sequenceMembersCountSaved)
                        {
                            Console.Write(numbers[numberIndex]);
                            sequenceMembersCount--;
                        }
                        else if (coefficient == 1 && sequenceMembersCount < sequenceMembersCountSaved)
                        {
                            if (numbers[numberIndex] >= 0)
                            {
                                Console.Write(" + " + numbers[numberIndex]);
                            }
                            else
                            {
                                Console.Write(" - " + (-numbers[numberIndex]));
                            }

                            if(sequenceMembersCount == 1)
                            {
                                Console.WriteLine(" = 0");
                            }
                            sequenceMembersCount--;
                        }
                    }
                }
            }
        }

        static int getBit(int coefficients, int bitIndex)
        {
            return (coefficients >> bitIndex) & 1;
        }

        static bool onlyOneBitSet(int coefficients)
        {
            int setBitCount = 0;
            int highestBit = 31;
            for(int i = 0; i <= highestBit; i++)
            {
                if(((coefficients >> i) & 1) == 1)
                {
                    setBitCount++;
                }
            }
            if(setBitCount == 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}