0

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!

Community
  • 1
  • 1
tdowek1
  • 557
  • 4
  • 7
  • 1
    Homework question... – jbrown Jan 07 '16 at 15:21
  • 2
    Oh, sure, one solution to the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem) coming right up... ;-P – deceze Jan 07 '16 at 15:21
  • Can you provide an English-like description of an algorithm that you think would do the job? –  Jan 07 '16 at 15:23
  • @torazaburo I have added in a description of the algorithm that I think would do the job at the bottom of the description. Thanks. – tdowek1 Jan 07 '16 at 15:42
  • @deceze Actually it's not the knapsack problem, it's the subset sum problem. I'm no expert in complexity theory, but my sense is that the condition that he wants to find a solution involving the largest values greatly simplifies this problem and it might not even be NP-complete anymore. –  Jan 07 '16 at 16:54
  • @torazaburo I knew someone was going to correct that statement. ;) – deceze Jan 07 '16 at 17:27

1 Answers1

2

The basic pattern for recursion is:

  1. Return known value for simple case(s). For this problem, the simple cases are (a) a target of 0 (solution is the empty array) and (b) a negative target (failure).
  2. Recurse and return some calculation based on the answer. For this problem, we look at each candidate value, and recurse with a target reduced by that value, returning an array composed of the result of the recursion with the addition of the current element.

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]
  • 1
    this works perfectly as I need it to. Thank you so much for your time in resolving it and patience in dealing with a completely novice programmer. I greatly appreciate it! – tdowek1 Jan 08 '16 at 16:55