- A+

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.