Reaching a target integer

Question

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

I also have a target random integer.

I need to get all the combinations which sum is greater or equal to the target without using unnecesary numbers. Given 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's 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've tried a lot of recursive strategies but I can't find a correct answer. No specific language is required, pseudocode is welcome.

EDIT: Posting code

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 which contains a name for each number. Padre.plazas is the number.

The array right now is [6,4,4,4,3,3,3], and the target is 8.

This seems to be quite similar to http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum — Hans, Oct 17 '12 at 09:11
It's kind of similar but it's not the same as what I want is to get if they're equal OR greater. I find this problem a lot more difficult. — Charlie-Blake, Oct 17 '12 at 09:13

Eduardo · Accepted Answer · 2012-10-17T13:00:46.237

3

I think something like this would 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;
}

edited Oct 17 '12 at 13:00

answered Oct 17 '12 at 08:50

Eduardo

8,362
6
38
72

But it prints the array even if it's not an optimal solution. I want to print only optimal ones. – Charlie-Blake Oct 17 '12 at 08:56
I understand now. Changed it to print only optimal solutions – Eduardo Oct 17 '12 at 09:00
I get a StackOverflowError when executing this :( – Charlie-Blake Oct 17 '12 at 09:11
How big is your array? It could go as deep as the number of elements you have in the array – Eduardo Oct 17 '12 at 09:13
It will contain between 3 and 10 elements, the testing one contains 8 elements. It only contains results with 2 or 3 elements. – Charlie-Blake Oct 17 '12 at 09:14
It is quite strange to get a stack overflow with so few elements. Could you post your code? – Eduardo Oct 17 '12 at 09:15
In your loop, you either need to start at i = `padres.size()-1` or loop while `i > 0` – Eduardo Oct 17 '12 at 09:28
Ok, I officially love you. Thank you very much!! – Charlie-Blake Oct 17 '12 at 09:40
Me alegro y muy buena suerte en tu proyecto. Saludos. – Eduardo Oct 17 '12 at 09:41

score 1 · Answer 2 · answered Oct 17 '12 at 08:59

An inefficient 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

Reaching a target integer

2 Answers2