How to add array values to equal a number, or fail if values in array wont work

Question

I am trying to build a calculator that will tell me what "steps" are needed to stack up to a given value. Using only that "steps" available in the array.

Example:

decimal[] blocks {.05, .100, .150, .200, .250}
goal = .550m

result = .100, .200, .250

I have tried using nested if statements and array find/last with not much luck. I can get a match if the goal is an exact match, or will match with two of them stacked. I can't get it to work for the max(.750).

This is what I have so far:

code:

        string result = "nope";
        decimal goal = 3.264m;
        decimal[] DAStep = new decimal[10];
        decimal temp = Array.Find(GaugeBlockArray, element => element.Equals(goal));
        if (temp != 0m)
        {
            DAStep[0] = Array.Find(GaugeBlockArray, element => element.Equals(temp));
            result = DAStep[0].ToString();
        }
        else
        {
            DAStep[0] = GaugeBlockArray.Last(element => element <= goal); ;

            decimal remaining;
            remaining = goal - DAStep[0];
            while (remaining != 0m)
            {
                DAStep[1] = GaugeBlockArray.Last(element => element <= remaining);
                if (DAStep[1] != remaining)
                {
                    DAStep[2] = GaugeBlockArray.Last(element => element <= (DAStep[1] - .0001m));
                    if (DAStep[2] == 0) { DAStep[1] = DAStep[2]; }
                }
            }
        }

GaugeBlockArray contains an array of 72 different elements from .05 to 4.0. And, I can only use each block once.

edit: I guess more detail on the array contents may help getting to a solution.

GaugeBlockArray: .05 .100 .1001 .1002 .1003 .1004 .1005 .1006 .1007 .1008 .1009 .110 .111 .112 .113 .114 .115 .116 .117 .118 .119 .120 .121 .122 .123 .124 .125 .126 .127 .128 .129 .130 .131 .132 .133 .134 .135 .136 .137 .138 .139 .140 .141 .142 .143 .144 .145 .146 .147 .148 .149 .150 .200 .250 .300 .350 .400 .450 .500 .550 .600 .650 .700 .750 .800 .850 .900 .950 1.000 2.000 3.000 4.000

Answer 1

Many thanks to @GeorgPatscheider for getting me pointed in the right direction!

This is my final working result:

public static void CountSum(decimal[] DNumbers, decimal Dsum)
    {

        foreach (Window window in Application.Current.Windows)
        {
            if (window.GetType() == typeof(MetTracker.GaugeCalc))
            {
                (window as MetTracker.GaugeCalc).CalculateBtn.Content = "working...";
            }
        }

        DNumbers = Array.ConvertAll(DNumbers, element => 10000m * element);
        string TempString = GetSettingsStrings("GBCMaxStep"); // only used to initialize max step value
        Dsum = Dsum * 10000m;
        Int32 Isum = Convert.ToInt32(Dsum);
        Int32[] INumbers = Array.ConvertAll(DNumbers, element => (Int32)element);
        // int result = 0;
            GetmNumberOfSubsets(INumbers, Isum);
        success = false;
        return;
    }

    private static void GetmNumberOfSubsets(Int32[] numbers, Int32 Isum)
    {
        set = numbers;
        sum = Isum;
        FindSubsetSum();
    }
    //-------------------------------------------------------------

    static Int32[] set;
    static Int32[] subSetIndexes;
    static Int32 sum;
    static Int32 numberOfSubsetSums;
    static bool success = false;
    static List<Int32> ResultSet = new List<Int32>();

    static List<string> results = new List<string>();//------------------------------------------------------------

    /*
        Method: FindSubsetSum()
    */
    private static void FindSubsetSum()
    {
        numberOfSubsetSums = 0;
        Int32 numberOfElements = set.Length;
        FindPowerSet(numberOfElements);
    }
    //-------------------------------------------------------------

    /*
        Method: FindPowerSet(int n, int k)
    */
    private static void FindPowerSet(Int32 n)
    {
        // Super set - all sets with size: 0, 1, ..., n - 1
        for (Int32 k = 0; k <= n - 1; k++)
        {
            subSetIndexes = new Int32[k];
            CombinationsNoRepetition(k, 0, n - 1);
            if(subSetIndexes.Length >= GBC_MaxStepSetting) {
                break; }
        }

        if (numberOfSubsetSums == 0)
        {
            MessageBox.Show("No subsets with wanted sum exist.");
        }
    }
    //-------------------------------------------------------------

    /*
        Method: CombinationsNoRepetition(int k, int iBegin, int iEnd);
    */
    private static void CombinationsNoRepetition(Int32 k, Int32 iBegin, Int32 iEnd)
    {
        if (k == 0)
        {
            PrintSubSet();
            return;
        }

        if (success == false)
        {
            for (Int32 i = iBegin; i <= iEnd; i++)
            {
                subSetIndexes[k - 1] = i;
                ++iBegin;
                CombinationsNoRepetition(k - 1, iBegin, iEnd);
                if (success == true)
                    break;
            }

        }
            return;
    }

    private static void PrintSubSet()
    {
        Int32 currentSubsetSum = 0;

        // accumulate sum of current subset
        for (Int32 i = 0; i < subSetIndexes.Length; i++)
        {
            currentSubsetSum += set[subSetIndexes[i]];
            if(currentSubsetSum > sum) { break; }
        }

        if(currentSubsetSum > sum) { return; }

        // if wanted sum: print current subset elements
        if (currentSubsetSum == sum)
        {
            ++numberOfSubsetSums;

            // results.Add("(");
            for (Int32 i = 0; i < subSetIndexes.Length; i++)
            {
               results.Add((set[subSetIndexes[i]]).ToString());
                ResultSet.Add(set[subSetIndexes[i]]);
                if (i < subSetIndexes.Length - 1)
                {
                    // results.Add(" ,");
                }
            }
            // results.Add(")");
            Int32[] ResultSetArr = ResultSet.ToArray();
            decimal[] ResultSetArrD = Array.ConvertAll(ResultSetArr, element => (decimal)element);
            ResultSetArrD = Array.ConvertAll(ResultSetArrD, element => element / 10000m);
            // var message = string.Join(Environment.NewLine, ResultSetArrD);
            // message = string.Format("{0:0.0000}", message);
            int l = ResultSetArrD.Length;
            string[] ResultString = new string[l];
            foreach(int i in ResultSetArrD)
            {ResultString = Array.ConvertAll(ResultSetArrD, element => element.ToString("0.0000"));}
            var message = string.Join(Environment.NewLine, ResultString);
            decimal ResultSum = ResultSetArrD.Sum();
            MessageBox.Show(message + "\n= " + ResultSum.ToString("0.0000"), "Result");
            Array.Clear(ResultSetArrD, 0, ResultSetArrD.Length);
            Array.Clear(ResultSetArr, 0, ResultSetArr.Length);
            ResultSet.Clear();
            message = null;
            success = true;
            foreach (Window window in Application.Current.Windows)
            {
                if (window.GetType() == typeof(MetTracker.GaugeCalc))
                {
                    (window as MetTracker.GaugeCalc).CalculateBtn.Content = "Calculate";
                }
            }
            return;
        }

        if (success == true)
            return;
    }

I added some limiting to reduce the amount of time before it reports a failure to find a combo. I also convert the array to a double to get around the headache the decimals were causing me. Works great!