# Solving The Subset Problem in php

Posted on

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 (  => 100  => 50  => 25  => 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