Getting all the combination of numbers from a list that would sum to a specific number

Question

I have the following list of numbers (1,3,4,5,7,9,10,12,15) and I want to find out all the possible combinations of 3 numbers from this list that would sum to 20.

My research on stackoverflow has led me to this post: Finding all possible combinations of numbers to reach a given sum

There is a solution provided by Mark which stand as follows:

subset_sum = function(numbers,target,partial=0){
if(any(is.na(partial))) return()
s = sum(partial)
if(s == target)  print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
if(s > target) return()
for( i in seq_along(numbers)){
n = numbers[i]
remaining = numbers[(i+1):length(numbers)]
subset_sum(remaining,target,c(partial,n))
}
}

However I am having a hard time trying to tweak this set of codes to match my problem. Or may be there is a simpler solution?

I want the output in R to show me the list of numbers.

Any help would be appreciated.

Answer 1

You can use combn function and filter to meet your criteria. I have performed below calculation in 2 steps but one can perform it in single step too.

v <-  c(1,3,4,5,7,9,10,12,15)
AllComb <- combn(v, 3)   #generates all combination taking 3 at a time.
PossibleComb  <- AllComb[,colSums(AllComb) == 20]  #filter those with sum == 20

#Result: 6 sets of 3 numbers (column-wise) 
PossibleComb
#      [,1] [,2] [,3] [,4] [,5] [,6]
# [1,]    1    1    1    3    3    4
# [2,]    4    7    9    5    7    7
# [3,]   15   12   10   12   10    9
# 

# Result in list
split(PossibleComb, col(PossibleComb))

# $`1`
# [1]  1  4 15
# 
# $`2`
# [1]  1  7 12
# 
# $`3`
# [1]  1  9 10
# 
# $`4`
# [1]  3  5 12
# 
# $`5`
# [1]  3  7 10
# 
# $`6`
# [1] 4 7 9

Answer 2

The combn also have a FUN parameter which we can describe to output as list and then Filter the list elements based on the condition

Filter(function(x) sum(x) == 20, combn(v, 3, FUN = list))
#[[1]]
#[1]  1  4 15

#[[2]]
#[1]  1  7 12

#[[3]]
#[1]  1  9 10

#[[4]]
#[1]  3  5 12

#[[5]]
#[1]  3  7 10

#[[6]]
#[1] 4 7 9

data

v <-  c(1,3,4,5,7,9,10,12,15)