R – find all combinations of a set of numbers that add up to a certain total

  • A+
Category:Languages

I've seen a few solutions to similar problems, but they all require iteration over the number of items to be added together.

Here's my goal: from a list of numbers, find all of the combinations (without replacement) that add up to a certain total. For example, if I have numbers 1,1,2,3,5 and total 5, it should return 5,2,3, and 1,1,3.

I was trying to use combn but it required you to specify the number of items in each combination. Is there a way to do it that allows for solution sets of any size?

 


I took your combn idea and looped over the possible sizes of the sets.

x = c(1,1,2,3,5,8,13) M = length(x)  y = NULL total = 15 for (m in 1:M){     tmp = combn(x, m)     ind = which(colSums(tmp) == total)     if (length(ind) > 0){         for (j in 1:length(ind))             y = c(y, list(tmp[,ind[j]]))         }     }  > y [[1]] [1]  2 13  [[2]] [1]  1  1 13  [[3]] [1] 2 5 8  [[4]] [1] 1 1 5 8  [[5]] [1] 1 1 2 3 8 

Obviously, this will have problems as M grows since tmp will get big pretty quickly and the length of y can't be (maybe?) pre-determined.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: