I am trying to generate all possible combinations of certain values in an array of 15 which add up to 50.

```
$a = [3, 4, 1, 2, 5]
print $a.repeated_permutation(15).to_a
```

In this case,

```
[2,2,2,2,4,4,4,4,4,4,4,4,4,3,3]
[2,2,2,4,2,4,4,4,4,4,4,4,4,3,3]
[2,2,4,2,2,4,4,4,4,4,4,4,4,3,3]
```

are all possible answers.

After some investigation I realize the code to do this is a bit over my head, but I will leave the question up if it might help someone else.

For some reference as to what I am working on, Project Euler, problem 114. It's pretty difficult, and so I am attempting to solve only a single case where my 50-space-long grid is filled only with 3-unit-long blocks. The blocks must be separated by at least one blank, so I am counting the blocks as 4. This (with some tweaking, which I have left out as this is confusing enough already) allows for twelve blocks plus three single blanks, or a maximum of fifteen elements.

# Best How To :

**Approach**

I think recursion is the way to go here, where your recursive method looks like this:

```
def recurse(n,t)
```

where

`n`

is the number of elements required; and
`t`

is the required total.

If we let `@arr`

be the array of integers you are given, `recurse(n,t)`

returns an array of all permutations of `n`

elements from `@arr`

that sum to `t`

.

**Assumption**

I have assumed that the elements of `@arr`

are non-negative integers, sorted by size, but the method can be easily modified if it includes negative integers (though performance will suffer). Without loss of generality, we can assume the elements of `@arr`

are unique, sorted by increasing magnitude.

**Code**

```
def recurse(n,t)
if n == 1
@arr.include?(t) ? [[t]] : nil
else
@arr.each_with_object([]) do |i,a|
break if i > t # as elements of @arr are non-decreasing
if (ret = recurse(n-1,t-i))
ret.each { |b| a << [i,*b] }
end
end
end
end
```

**Examples**

```
@arr = [3, 4, 1, 2, 5].sort
#=> [1, 2, 3, 4, 5]
recurse(1,4)
#=> [[4]]
recurse(2,6)
#=> [[1, 5], [2, 4], [3, 3], [4, 2], [5, 1]]
recurse(3,10)
#=> [[1, 4, 5], [1, 5, 4], [2, 3, 5], [2, 4, 4], [2, 5, 3],
# [3, 2, 5], [3, 3, 4], [3, 4, 3], [3, 5, 2], [4, 1, 5],
# [4, 2, 4], [4, 3, 3], [4, 4, 2], [4, 5, 1], [5, 1, 4],
# [5, 2, 3], [5, 3, 2], [5, 4, 1]]
recurse(3,50)
#=> []
```

**Improvement**

We can do better, however, by first computing all combinations, and then computing the permutations of each of those combinations.

```
def combo_recurse(n,t,last=0)
ndx = @arr.index { |i| i >= last }
return nil if ndx.nil?
arr_above = @arr[ndx..-1]
if n == 1
arr_above.include?(t) ? [[t]] : nil
else
arr_above.each_with_object([]) do |i,a|
break if i > t # as elements of @arr are non-decreasing
if (ret = combo_recurse(n-1,t-i,i))
ret.each { |b| a << [i,*b] }
end
end
end
end
combo_recurse(1,4)
#=> [[4]]
combo_recurse(2,6)
#=> [[1, 5], [2, 4], [3, 3]]
combo_recurse(3,10)
#=> [[1, 4, 5], [2, 3, 5], [2, 4, 4], [3, 3, 4]]
combo_recurse(3,50)
#=> []
combo_recurse(15,50).size
#=> 132
combo_recurse(15,50).first(5)
#=> [[1, 1, 1, 1, 1, 1, 4, 5, 5, 5, 5, 5, 5, 5, 5],
# [1, 1, 1, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5],
# [1, 1, 1, 1, 1, 2, 4, 4, 5, 5, 5, 5, 5, 5, 5],
# [1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5],
# [1, 1, 1, 1, 1, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5]]
```

We can then compute the permutations from the combinations:

```
combo_recurse(2,6).flat_map { |a| a.permutation(a.size).to_a }.uniq
#=> [[1, 5], [5, 1], [2, 4], [4, 2], [3, 3]]
combo_recurse(3,10).flat_map { |a| a.permutation(a.size).to_a }.uniq
#=> [[1, 4, 5], [1, 5, 4], [4, 1, 5], [4, 5, 1], [5, 1, 4],
# [5, 4, 1], [2, 3, 5], [2, 5, 3], [3, 2, 5], [3, 5, 2],
# [5, 2, 3], [5, 3, 2], [2, 4, 4], [4, 2, 4], [4, 4, 2],
# [3, 3, 4], [3, 4, 3], [4, 3, 3]]
```

We can approximate the number of permutations for `(15,50)`

(it will be somewhat high because `uniq`

is not applied):

```
def factorial(n)
(1..n).reduce :*
end
Math.log10 combo_recurse(15,50).reduce(1) { |t,a| t*factorial(a.size) }
#=> 1599.3779486682888
```

That is, the result has about 1,600 digits. What platform will you be running this on?