Solving The Subset Problem in php

The subset problem is thus;

Given that I have an array of values [100, 50, 25, 10, 1]

And I have the target of 176 can i make 176 out of my subset values.?

Looking at this simple example you can see that, that is intact the case. The subset of 176 is [100, 50, 25, 1]

But lets solve this programatically;

<?php

function subset($target_number, $subset) {

    $total_of_numbers_used = 0;
    $numbers_used = [];

    foreach($subset as $subset_number) {
        if(($total_of_numbers_used + $subset_number) <= $target_number) {
        $total_of_numbers_used += $subset_number;
            $numbers_used[] = $subset_number;
        }
    }
    return compact('total_of_numbers_used', 'numbers_used');
}

// The number we want to find
$target_number = 176;

// our subset, MUST be descending
$sub_set = [100, 50, 25, 1];

print_r(subset($target_number, $sub_set));
// output: Array ( [total_of_numbers_used] => 176 [numbers_used] => Array ( [0] => 100 [1] => 50 [2] => 25 [3] => 1 ) )

So yes i can make the number 176 out of 100, 50, 25, and 1. I do not need 10

In pseudo code it may look something like

Setup 1. set target_number <— this is what we are trying to hit 2. set a total_number <— this is what we will continuously add to, in an attempt to try and make our total number 3. set numbers_used <— this will keep a track of which numbers we have used to make up our final answer

1. loop through that subset going from highest to lowest set iteration as current_number
2. if current_number + total_number is less than or equal to the number we are trying to achieve set total_number = (current_number + total_number) and push number into numbers_array
3. move back to step 2 until current_number + total_number is greater than target_number

What this is good for;

The Travelling salesman problem Factorising Computing change