# Picking n integers from n different sets summing to a given value

Given a set of integers $\{l_1,l_2,\ldots,l_n\}$, where each integer is associated with a set $m_k\in\{-l_k,-l_k+1,\ldots,l_k\}$, I need to find all combinations $\{m_1,m_2,\ldots,m_n\}$ that sum to a given integer $M$.

As an example, let's say the input is $\{1,3\}$ and $M=2$. This means that $m_1\in\{-1,0,1\}$ and $m_2\in\{-3,-2,\ldots,3\}$. The desired combinations are then:

$\{m_1,m_2\}=\{-1,3\},\{0,2\},\{1,1\}$.

For only two integers $l_1$ and $l_2$ this is easy, but a bit more involved for a general number. I have a brute force algorithm implemented which finds all possible combinations and then picks those with the right sum, but this quickly becomes too slow when the sets grow.

So I'm wondering if there is a fast algorithm to find these (doesn't have to be the fastest in existence if sacrificing a little speed gives one easier to implement)?

I'm sure this is a well known problem, but googling I couldn't find anything.

• If you view this problem as a forward directed graph, with each $m_i$ representing a column of nodes, one could create a more efficient algorithm using a dynamic programming approach. – spektr Mar 30 '16 at 15:57
• Isn't what you have here just a variation on the Knapsack problem? – Wolfgang Bangerth Mar 30 '16 at 18:49

I thought this might be a fun problem to solve, so I cranked out a solution for it based on the comment I made in the problem statement. The class representing the solution, which is in C++, can be found via the following link:

Combinatorial Solution Class

The main.cpp file can be written with the following example code:

#include <stdio.h>
#include "CombinatorialSoln.hpp"

int main( int argc, char** argv ){

// Initialize combinatorial problem
CombinatorialSoln soln;
std::vector<int> iset {1, 3, 2, 5, 6, 3};
soln.setIntegerSet(iset);

// Compute combinations
CombinatorialSoln::Combos combos = soln.computeCombinations(-5);

// print results
for(int i = 0; i < combos.size(); i++ ){
combos[i].print();
}

// Print basic results
soln.showStatistics();

// Complete
return 1;
}

• This is great! Now I wonder is there a way to either make this work either with half-integer l (so that e.g. l_1=3/2 and m_1 in {-3/2 -1/2 1/2 3/2}, or to make it so that one can switch m to "jumps of 2"; i.e. so that if e.g. l_1=5 it is possible using a flag to make m_1 in {-5, -3, -1, 1, 3, 5} ? (not part of the OP I know) – jorgen Mar 31 '16 at 8:59
• I suspect it wouldn't be too hard to modify the jump value to become an input that is used for each m set. It would only change some of the helper function logic in my mind. – spektr Mar 31 '16 at 13:52