Reputation: 577
I am trying to find a subset of values within an array which add up to a given number and return an array of that subset. I need the return array to contain the highest possible largest value.
The integer array will always be in ascending order but there will not always be a valid answer. If there is no valid answer I need to return a string along the lines of 'No valid answer'.
For example:
If the int array is: [1, 2, 3, 5, 7, 9, 11]
and the target is 19
- I want the return array to be [1, 7, 11]
.
I would not like to return [9, 7, 3]
because 11
is larger than 9
, and I would not like to return [3, 5, 11]
because 7
is larger than 5
.
I am assuming that I will need a for loop within a recursive function to get my answer but have been unable to figure out how to do it.
I have found variations of the question in Java: https://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target
I have also found a solution in JavaScript which returns pairs of values (although this is pretty straight forward): https://codereview.stackexchange.com/questions/74152/given-an-array-of-integers-return-all-pairs-that-add-up-to-100
I was thinking that you would need to start your loop with the last element of the array and loop backwards through the array to check if there is a combination of 2 numbers whose sum is the target.
If there is not a pair, you would need to start with the highest pair of numbers whose sum is less that the target and loop though the array to find if there is a combination.
This operation would need to be continued until the subset is found or you discover that there is no valid answer.
Please help!
Upvotes: 0
Views: 2111
Reputation:
The basic pattern for recursion is:
So:
// Find subset of a that sums to n.
function subset_sum(n, a) {
// SIMPLE CASES
if (n < 0) return null; // Nothing adds up to a negative number
if (n === 0) return []; // Empty list is the solution for a target of 0
// RECURSIVE CASE
a = a.slice();
while (a.length) { // Try remaining values
var v = a.shift(); // Take next value
var s = subset_sum(n - v, a); // Find solution recursively
if (s) return s.concat(v); // If solution, return
}
}
To enforce the rule that you want to prefer higher values first, pass this function an array of values that is pre-sorted in descending order.
> subset_sum(19, [11, 9, 7, 5, 3, 2, 1])
< [1, 7, 11]
Upvotes: 2