Finding all possible combinations of numbers from a vector to reach a given sum (No repetitions)

Question

I have a vector "numbers" and I want to find out all the possible combinations of 1,2 or 3 numbers that would sum in the range of 90 to 110.

I know there are plenty of posts with ways to solve the problem, but none of them do what I need. At least not in R#

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10);
names(numbers) <- c("A","B","C","D","E","F","G","H","I","J","K","L")

The result should look like this:

A + B
A + D
A + H
I
B + E
B + F
C + H
C + J
C + K
D + E
D + F
F + H
F + K
J + L

Answer 1

In the code below, we identify combinations of values with sums in the desired range and then get the indices of those combinations. We then use the indices to get the names of the elements that we want to sum together. lapply takes care of iterating over each number of values that we want to sum together.

This is packaged into a function where x is the named vector of numbers, n is the maximum number of values you want to sum together, and interval is the range that the sums should be in.

Note that the function below returns strings of the form "A + B", as described in your question. If your goal is to do additional processing on the combinations of letters, you'll probably be better off working directly with the matrices (or lists) of combinations returned by combn().

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10);
names(numbers) <- LETTERS[1:length(numbers)]

library(dplyr) # For between function

combos = function(x, n, interval) {

  res = lapply(2:n, function(i) {
    cc = combn(x, i)
    idx = which(between(colSums(cc), interval[1], interval[2]))
    apply(combn(names(x), i)[ , idx], 2, paste, collapse=" + ")
  })

  cbind(unlist(c(names(x)[between(x, interval[1], interval[2])], res)))
}

combos(numbers, 3, c(90, 110))

     [,1]       
 [1,] "I"        
 [2,] "A + B"    
 [3,] "A + D"    
 [4,] "A + H"    
 [5,] "B + E"    
 [6,] "B + F"    
 [7,] "C + H"    
 [8,] "C + J"    
 [9,] "C + K"    
[10,] "D + E"    
[11,] "D + F"    
[12,] "F + H"    
[13,] "F + K"    
[14,] "G + I"    
[15,] "G + J"    
[16,] "I + L"    
[17,] "J + L"    
[18,] "A + B + G"
[19,] "A + B + L"
[20,] "A + C + E"
[21,] "A + C + F"
[22,] "A + D + G"
[23,] "A + E + G"
[24,] "A + E + L"
[25,] "B + C + F"
[26,] "B + C + L"
[27,] "B + E + G"
[28,] "B + F + G"
[29,] "B + F + L"
[30,] "C + D + G"
[31,] "C + D + L"
[32,] "C + E + F"
[33,] "C + G + H"
[34,] "C + G + J"
[35,] "C + G + K"
[36,] "C + H + L"
[37,] "C + K + L"
[38,] "D + F + G"
[39,] "D + F + L"
[40,] "F + G + H"
[41,] "F + G + K"
[42,] "F + H + L"
[43,] "G + J + L"
[44,] "G + K + L"

set.seed(2)
nn = rnorm(10)
names(nn) = LETTERS[1:length(nn)]

combos(nn, 3, c(2,2.5))

      [,1]       
 [1,] "B + I"    
 [2,] "C + G"    
 [3,] "F + I"    
 [4,] "B + C + G"
 [5,] "B + E + I"
 [6,] "B + F + I"
 [7,] "B + I + J"
 [8,] "C + D + I"
 [9,] "C + E + G"
[10,] "C + F + G"
[11,] "C + G + H"
[12,] "C + G + J"
[13,] "E + F + I"
[14,] "G + H + I"

Answer 2

A recursive option without generating all combinations. Might be memory efficient but surely not fast.

gen <- function(chosen, rest, lb, ub) {

    new_ub <- ub - sum(chosen)

    rest <- rest[-match(chosen[1L], rest)]

    if (new_ub < 0 || length(chosen) > 2L || !any(rest <= new_ub)) {
        if (sum(chosen) >= lb && sum(chosen) <= ub) {
            return(list(chosen[order(names(chosen))]))
        }
        return(NULL)
    }

    ret <- c()
    for (x in names(rest[rest <= new_ub])) {
        ret <- c(ret, gen(c(rest[x], chosen), rest, lb, ub))
        if (sum(chosen) >= lb && sum(chosen) <= ub) {
            ret <- c(list(chosen[order(names(chosen))]), ret)
        }
    }
    ret
}

ans <- unique(unlist(
    lapply(names(numbers), function(x) gen(numbers[x], rest=numbers, lb=90, ub=110)),
    recursive=FALSE))
unique(sapply(ans, function(x) paste(sort(names(x)), collapse=" + ")))

output:

 [1] "A + B"     "A + B + G" "A + B + L" "A + C + E" "A + C + F" "A + D"     "A + D + G"
 [8] "A + E + G" "A + E + L" "A + H"     "B + C + F" "B + C + L" "B + E"     "B + E + G"
[15] "B + F"     "B + F + G" "B + F + L" "C + D + G" "C + D + L" "C + E + F" "C + G + H"
[22] "C + G + J" "C + G + K" "C + H"     "C + H + L" "C + J"     "C + K"     "C + K + L"
[29] "D + E"     "D + F"     "D + F + G" "D + F + L" "F + G + H" "F + G + K" "F + H"    
[36] "F + H + L" "F + K"     "G + I"     "G + J"     "G + J + L" "G + K + L" "I"        
[43] "I + L"     "J + L"    

Answer 3

I authored a package called RcppAlgos that is built for these tasks. There is a function comboGeneral that is able to find all combinations under a particular constraint. Observe:

comboBetween <- function(v, m, constraint) {
    do.call(c, lapply(1:m, function(x) {
        nums <- comboGeneral(v, x, constraintFun = "sum", 
                                   comparisonFun = c(">=", "<="), 
                                   limitConstraints = constraint)
        apply(matrix(myNames[match(nums, numbers)], 
                     ncol = x), 1, paste, collapse = " + ")
    }))
}

Here is an example:

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10);
myNames <- c("A","B","C","D","E","F","G","H","I","J","K","L")

comboBetween(numbers, 4, c(90, 110))
 [1] "I"             "G + J"         "G + I"         "L + J"         "L + I"         "C + H"        
 [7] "C + K"         "C + J"         "F + B"         "F + D"         "F + H"         "F + K"        
[13] "A + B"         "A + D"         "A + H"         "E + B"         "E + D"         "G + L + K"    
[19] "G + L + J"     "G + C + D"     "G + C + H"     "G + C + K"     "G + C + J"     "G + F + B"    
[25] "G + F + D"     "G + F + H"     "G + F + K"     "G + A + E"     "G + A + B"     "G + A + D"    
[31] "G + E + B"     "L + C + B"     "L + C + D"     "L + C + H"     "L + C + K"     "L + F + B"    
[37] "L + F + D"     "L + F + H"     "L + A + E"     "L + A + B"     "C + F + A"     "C + F + E"    
[43] "C + F + B"     "C + A + E"     "G + L + C + B" "G + L + C + D" "G + L + C + H" "G + L + C + K"
[49] "G + L + F + E" "G + L + F + B" "G + L + F + D" "G + L + A + E" "G + C + F + A" "G + C + F + E"
[55] "G + C + A + E" "L + C + F + A" "L + C + F + E"

It is quite efficient as well as it is written in C++ for maximal performance.

Answer 4

Here is a solution for the two and three number combination. I leave it up to the reader for 1 number combination case:

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10)
numnames<- c("A","B","C","D","E","F","G","H","I","J","K","L")

#Take 2 at a time
#Find all combinations of 2 each (output is a matrix)
c2<-combn(numbers, 2)
#find column positions which match the critera
mymatch<-which(colSums(c2)>=90 & colSums(c2)<=110)

#get results of letter comibnations
#combn(numnames, 2) will generate the same squence order as combn(numbers, 2)
answer2<-apply(combn(numnames, 2)[,mymatch], 2, function(t){print(t)
  paste(t, collapse = "+" )})

#Repeat taking 3 at a time
c3<-combn(numbers, 3)
mymatch<-which(colSums(c3)>=90 & colSums(c3)<=110)

answer3<-apply(combn(numnames, 3)[,mymatch], 2, function(t){print(t)
  paste(t, collapse = "+" )})

print(c(answer2, answer3))

[1] "A+B"   "A+D"   "A+H"   "B+E"   "B+F"   "C+H"   "C+J"   "C+K"   "D+E"   "D+F"   "F+H"   "F+K"   "G+I"    
[14] "G+J"   "I+L"   "J+L"   "A+B+G" "A+B+L" "A+C+E" "A+C+F" "A+D+G" "A+E+G" "A+E+L" "B+C+F" "B+C+L" "B+E+G"
[27] "B+F+G" "B+F+L" "C+D+G" "C+D+L" "C+E+F" "C+G+H" "C+G+J" "C+G+K" "C+H+L" "C+K+L" "D+F+G" "D+F+L" "F+G+H"
[40] "F+G+K" "F+H+L" "G+J+L" "G+K+L"

Answer 5

I would create a list of all the possible m combination of n elements (m = 1, 2, 3) using combn. You can then sum the elements in each tuple and filter them by the desired range. Sorry for the very approximate answer as I do not have access to a PC at the moment.