# Help getting matrix combinations that sum to X

**URL:** <https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789>\
**Category:** General Usage\
**Created:** [May 2, 2019, 6:37pm UTC](https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789 "2019-05-02T18:37:49Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [May 2, 2019, 6:37pm UTC](https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789/1 "2019-05-02T18:37:49Z")

</div>

I am trying to find all possible combinations of a matrix where the values sum to some target. It seems rather straightforward but the solution does elude me at the moment. Here is an example matrix. In this example, I’d like to find all possible matrix positions where the sum is 100. A “position” is taking one value from each column. So, trivially I can get that `((1,1),(5,2),(5,3),(5,4),(5,5))` and those like it are possible combinations. But finding all of them is escaping me…

Would anyone be willing to help?

```julia
julia> N = 5
5

julia> L = 5
5

julia> spots = repeat(reverse(collect(range(0,100,length=L))),1,N)
5×5 Array{Float64,2}:
 100.0 100.0 100.0 100.0 100.0
  75.0 75.0 75.0 75.0 75.0
  50.0 50.0 50.0 50.0 50.0
  25.0 25.0 25.0 25.0 25.0
   0.0 0.0 0.0 0.0 0.0

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 2, 2019, 7:01pm UTC](https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789/2 "2019-05-02T19:01:31Z")

</div>

The problem statement isn’t clear to me. What is a “combination of a matrix”? Likewise can you clarify what “A ‘position’ is taking one value from each column” means?

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [May 2, 2019, 7:16pm UTC](https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789/3 "2019-05-02T19:16:47Z")

</div>

More concretely, find all possible i\_1,...,i\_N in ((i\_1,1),(i\_2,2),...,(i\_N,N)) (in this particular case, a collection of 5 cartesian indices) such that the sum of the values at those spots in matrix equals 100.

So the example from the first post is “trivial” because the sum of `((1,1),(5,2),(5,3),(5,4),(5,5))` is `100 + 0 + 0 + 0 + 0`.

Another possibility is `((4,1),(4,2),(4,3),(4,4),(5,5))` which sums to `25 + 25 + 25 + 25 + 0`.

The columns are always going to be identical, if that helps.

---

<div class="post-metadata">

**Author:** ![JackDevine](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jackdevine/32/1048_2.png) [@JackDevine](https://discourse.julialang.org/u/JackDevine)\
**Post date:** [May 3, 2019, 3:17am UTC](https://discourse.julialang.org/t/help-getting-matrix-combinations-that-sum-to-x/23789/4 "2019-05-03T03:17:16Z")

</div>

I believe that this code will solve your problem:

```julia
using Combinatorics

L = 5
N = 5
spots = repeat(reverse(collect(range(0,stop=100,length=L))),1,N)

linear_inds = []
for n in 1:N^2
    combs = combinations(1:N^2,n)
    for comb in combs
        if sum(spots[comb]) == 100
            push!(linear_inds,comb)
        end
    end
end
# Check that the linear indices have the desired propoerty.
for i in 1:length(linear_inds)
    @assert sum(spots[linear_inds[i]]) == 100
end

```

If you want to convert the linear indices back into cartesian indices, then you can use this:

```julia
CartesianIndices(spots)[linear_inds[1][1]]

```

I only just noticed that you said that the columns will always be the same. I think that based on the above you could exploit that property to get a speed boost. In fact, there are a lot of changes that you could make to improve speed.