javascript - Find the highest subset of an integer array whose sums add up to a given target -

i trying find subset of values within array add given number , return array of subset. need return array contain highest possible largest value.

the integer array in ascending order there not valid answer. if there no valid answer need return string along lines of 'no valid answer'.

for example:

if int array is: [1, 2, 3, 5, 7, 9, 11] , target 19 - want return array [1, 7, 11]. not return [9, 7, 3] because 11 larger 9, , not return [3, 5, 11] because 7 larger 5.

i assuming need loop within recursive function answer have been unable figure out how it.

i have found variations of question in java: https://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target

i have found solution in javascript returns pairs of values (although pretty straight forward): https://codereview.stackexchange.com/questions/74152/given-an-array-of-integers-return-all-pairs-that-add-up-to-100

i thinking need start loop last element of array , loop backwards through array check if there combination of 2 numbers sum target.

if there not pair, need start highest pair of numbers sum less target , loop though array find if there combination.

this operation need continued until subset found or discover there no valid answer.

please help!

the basic pattern recursion is:

1. return known value simple case(s). problem, simple cases (a) target of 0 (solution empty array) , (b) negative target (failure).
2. recurse , return calculation based on answer. problem, @ each candidate value, , recurse target reduced value, returning array composed of result of recursion addition of current element.

so:

// find subset of sums n. function subset_sum(n, a) {   // simple cases   if (n < 0)   return null;       // nothing adds negative number   if (n === 0) return [];         // empty list solution target of 0    // recursive case   = 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 rule want prefer higher values first, pass function array of values pre-sorted in descending order.

> subset_sum(19, [11, 9, 7, 5, 3, 2, 1]) < [1, 7, 11]