Reaching Target Integer

Question

I have an array of random length full of random numbers. For simplicity, they are ordered from highest to lowest.

I also have a target random integer.

I need to get all combinations whose sum is greater than or equal to the target without using unnecessary numbers. In this example:

nums = [10, 6, 5, 3, 2, 1, 1] target = 8 

I want this output:

 10 (10 is higher or equal to 8, so there no need to sum it) 6+5 6+3 6+2 6+1+1 5+3 5+2+1 5+2+1 (Note that this result is different from the previous since there are 2 1s) 

I have tried many recursive strategies, but I cannot find the correct answer. No specific language is required, pseudo-code is welcome.

EDIT: Code Posting

 private static boolean filtrar(final CopyOnWriteArrayList<Padre> padres) { if (sum(padres) < TARGET) { return false; } int i; for (i = padres.size(); i >= 0; i--) { if (!filtrar(copiaPadresSinElemento(padres, i-1))) { break; } } // Solución óptima, no se puede quitar nada. if (i == padres.size()) { print(padres); } return true; } private static int sum(final CopyOnWriteArrayList<Padre> padres) { int i = 0; for (final Padre padre : padres) { i += padre.plazas; } return i; } private static void print(final CopyOnWriteArrayList<Padre> padres) { final StringBuilder sb = new StringBuilder(); for (final Padre padre : padres) { sb.append(padre); sb.append(", "); } final String str = sb.toString(); System.out.println(str); } private static CopyOnWriteArrayList<Padre> copiaPadresSinElemento( final CopyOnWriteArrayList<Padre> padres, final int i) { final CopyOnWriteArrayList<Padre> copia = new CopyOnWriteArrayList<Padre>(); for (int e = 0; e < padres.size(); e++) { if (e != i) { copia.add(padres.get(e)); } } return copia; } 

Padre is a simple object that contains a name for each number. Padre.plazas number is a number.

Now the array has the value [6,4,4,4,3,3,3], and the target is 8.

Answer 1

I think something like this will work:

 function filter(array, target): Boolean{ //assumes array is sorted in descending order if(sum(array) < target) return false; for(i = array.length-1; i>=0; --i){ if(! filter(array.createCopyRemovingElementAt(i), target)) break; } if(i==array.length-1) print(array); // solution is "optimal": could not remove a single number return true; } 

Answer 2

Ineffective solution: Complexity = O ((2 ^ n) * n)

 for i = 0 to 2^size-of-array do sum = 0 for j = 0 to n-1 do if(jth bit in i is 1) then sum+=array[j] fi done if(sum>=target) print the number i (uniquely identifies the set of numbers) done