Generating all combinations of list of numbers where the sum of the combination is <= N

Question

I have ArrayList<int> that contains all numbers that can be used in the combinations. I want to generate all possible combinations of these numbers of different length (number of integers), but all must have sum closest to N, but <= N (N is a input number). All numbers of the list have to be used (and only) once.

EXAMPLE

N = 10
list = {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7}

One combination will be (1, 5, 4), (3, 6), (9), (7), (4, 3), (8, 2), (1, 6, 3), (7)

Can anyone help me with the solution? I'm thinking of some recursive implementation. Am I on the right track?

EDIT

OK, because I can't explain this problem exactly as I want :) let's make it simpler. How to generate all sub-lists that have sum <= N, and can contain each number of the list only once. I'll do the rest of the work myself.

Is it just coincidental that all the subsets consists of consecutive elements from the input, or is this a requirement? (e.g. would 1,5,3 also be a valid subset?). Also, note that what you're asking is not the same as your example. — Bernhard Barker, Mar 05 '13 at 13:17
Yes, it is coincidental. I just wrote this as an example. (1, 5, 3) is also a valid subset. The important things are to use all of the numbers, use each number only once, the sum of the subset to be less then or equal to N, but the closest possible to N — nikmin, Mar 05 '13 at 13:22
@nikmin will (1, 5, 4), (3, 6), (9), (7, 3), (4), (8, 2), (1, 6, 3), (7) a possible combination. And what you have to say about (1), (5), (4), (3), (6), (9), (7), (4), (3), (8), (2), (1), (6), (3), (7) — Aman Deep Gautam, Mar 05 '13 at 13:49
@AmanDeepGautam The first one I think should be valid. The second one is not. I want to get the best (sum closest to N) combination in every moment. Some thing like using the greedy algorithm, but I don't want to use it because it won't give me the best combinations. My goal is to get the subsets in way that if I do `Sum(N-Sum(subset))` I will get the minimum — nikmin, Mar 05 '13 at 14:00
first you must sort your list and divide from maximum number to minimum number that each part length close to n.this problem like as [this](http://stackoverflow.com/questions/15175066/given-n-absolute-values-of-integers-find-the-combination-of-n-2-negative-and-n-2/15175585#15175585) problem. — amin k, Mar 05 '13 at 14:08

score 1 · Accepted Answer · answered Mar 05 '13 at 14:19

A simple k-combination of a finite set S is a subset of k distinct elements of S. Specifying a subset does not arrange them in a particular order.

You can use the CombinatoricsLib. CombinatoricsLib is a java library for generating combinatorial objects. https://code.google.com/p/combinatoricslib/

Using this:

    public static void main(String[] args) {

           // Create the initial vector
           ICombinatoricsVector<Integer> initialVector = Factory.createVector(
              new Integer[]  {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7} );          

           int subsetMaxSize = 5;
           int upperLimit = 10;  
           int lowerLimit = 8;
           for(int i = 1; i <= subsetMaxSize; i++)
           {
               Generator<Integer> gen = Factory.createSimpleCombinationGenerator(initialVector, i);
               for (ICombinatoricsVector<Integer> combination : gen)
               {
                   int sum = vectorSum(combination);
                   if(validateSum(sum, lowerLimit, upperLimit))
                       printVector(combination);
               }   
           }
    }

    public static boolean validateSum(Integer value, Integer lowerLimit, Integer upperLimit)
    {
        if(value <= upperLimit && value > lowerLimit)   
            return true;
        return false;           
    }

    public static Integer vectorSum(ICombinatoricsVector<Integer> vect)
    {
        Integer sum = 0;    
        for(int i = 0; i < vect.getSize(); i++) 
            sum += vect.getValue(i);
        return sum;
    }

    public static void printVector(ICombinatoricsVector<Integer> vect)
    {
        String output = ""; 
        for(int i = 0; i < vect.getSize(); i++)
            output += vect.getValue(i) + ", ";
        System.out.println(output);
    }

will return the output

9, 
1, 9, 
1, 8, 
5, 4, 
5, 4, 
4, 6, 
4, 6, 
3, 6, 
3, 7, 
3, 6, 
3, 7, 
6, 4, 
6, 3, 
6, 3, 
9, 1, 
7, 3, 
7, 2, 
7, 3, 
4, 6, 
3, 6, 
3, 7, 
8, 2, 
8, 1, 
2, 7, 
6, 3, 
3, 7, 
1, 5, 4, 
1, 5, 3, 
1, 5, 4, 
1, 5, 3, 
1, 5, 3, 
1, 4, 4, 
1, 3, 6, 
1, 3, 6, 
1, 6, 3, 
1, 6, 2, 
1, 6, 3, 
1, 7, 2, 
1, 7, 1, 
1, 3, 6, 
1, 8, 1, 
1, 2, 6, 
1, 2, 7, 
1, 1, 7, 
1, 6, 3, 
5, 4, 1, 
5, 3, 2, 
5, 3, 1, 
5, 4, 1, 
5, 3, 2, 
5, 3, 1, 
5, 2, 3, 
5, 1, 3, 
4, 3, 3, 
4, 3, 2, 
4, 3, 3, 
4, 4, 2, 
4, 4, 1, 
4, 3, 2, 
4, 3, 3, 
4, 2, 3, 
3, 6, 1, 
3, 4, 3, 
3, 4, 2, 
3, 4, 3, 
3, 3, 3, 
3, 1, 6, 
6, 3, 1, 
6, 2, 1, 
6, 1, 3, 
7, 2, 1, 
4, 3, 2, 
4, 3, 3, 
4, 2, 3, 
3, 1, 6, 
2, 1, 6, 
2, 1, 7, 
1, 6, 3, 
1, 5, 3, 1, 
1, 5, 3, 1, 
1, 5, 2, 1, 
1, 5, 1, 3, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 4, 1, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 2, 3, 
1, 4, 1, 3, 
1, 3, 4, 2, 
1, 3, 4, 1, 
1, 3, 3, 2, 
1, 3, 3, 3, 
1, 3, 2, 3, 
1, 6, 2, 1, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 2, 3, 
1, 4, 1, 3, 
1, 3, 2, 3, 
1, 2, 1, 6, 
4, 3, 2, 1, 
4, 3, 2, 1, 
4, 2, 1, 3, 
3, 4, 2, 1, 
3, 3, 2, 1, 
3, 3, 1, 3, 
3, 2, 1, 3, 
4, 3, 2, 1, 
4, 2, 1, 3, 
3, 2, 1, 3, 
1, 3, 3, 2, 1, 
1, 3, 2, 1, 3, 
1, 3, 2, 1, 3,

score 0 · Answer 2 · answered Mar 05 '13 at 14:10

You can use recursion, however if you will tell what is your original problem and the constraints, then there could be a better solution. For recursion it will be something like this:

list = {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7};
result = {};

function rec(index, max_sum) {
    if(index >= list.length) {
        print result;
        return;
    }
    for each list[i] where i >= index {
        // Case 1 - we take current element and go further
        if(list[i] <= max_sum) {
            result.insert(list[i]);
            rec(index + 1, max_sum - list[i]);
            result.remove(list[i]);
        }

        // Case 2 - we skip current element
        rec(index + 1, max_sum);
    }
}

N = 10;
rec(0, N);

This will just generate all possible combinations of numbers sum of which doesn't exceed N.

Generating all combinations of list of numbers where the sum of the combination is <= N

2 Answers2