*Moved this from the New to Julia to a more fitting section*

I’m trying to translate a divide and conquer algorithm for a modified subset sum problem from Python. A simplified version might look like this: You are given an array of structs with a mass attribute, and a float *target*. Your task is to return **all** of the subsets of the input array whose mass adds up to the *target*, save for some small allowed error.

The model solution is to recursively traverse the entire array, branching off on each element, either including it in the solution and lowering the target by its mass, or skipping it. If you want to find every solution, the naive algorithm just assembles the solutions from both branches:

```
function subset_sum(objects, target, chosen)
if very_close_to_zero(target)
return [chosen]
elseif target < 0 || length(objects) == 0
return []
else
first, rest = objects[1], objects[2:end]
return [
subset_sum(rest target, chosen) ;
subset_sum(rest, target - first.mass, push(chosen, first))
]
end
end
```

But I assume this will be very allocation heavy. Is there a better Julian-esque solution? In Python I ended up doing basically this, only passing down the accumulator as a tuple because of the immutability, and appending `chosen`

to a global result array instead of returning it.

Note that although dynamic programming would help in this model problem, my specific task doesn’t mesh well with it because I have to keep track of a lot of additional stuff, like limited number of skipped objects, each object actually having several possible masses (and I can choose whichever one I need), etc. If you’re interested, I’d be glad to be proven wrong in this regard, but it might be better suited for another discussion.