Как найти все комбинации суммы элементов подмассивов?

Question

[Михаил]

mas = [[1,2], [1,2,3], [1,2]

Визуально

Как пример, необходимо найти всевозможные комбинации суммы числа 6 из различных подмассивов.

6:
1) 1, 3 , 2
2) 2, 2, 2
3) 2, 3 1
...

Пока что представляю себе это в виде векторов с нахождением всех возможных вариантов, но с реализацией сообразить не могу. Понимаю, что надо копать в сторону рекурсивных функций. Буду очень благодарен за помощь :)

Answer 1

[GreatRash]

https://www.youtube.com/watch?v=p8SDPaX1wgw

Comments

[Михаил]

Всё же, здесь немного не поиск комбинаций массива, а поиск всевозможных комбинаций всей матрицы (если так можно выражаться :) )

Answer 2

[Александр Скуснов]

Вам надо запустить монадическое вычисление для списка. Если питонисты не ответят, то поспрашивайте хаскелистов. (Сам решил третий раз пройти курс на Степике по Хаскелю, т.к. монады это тихий ужас).

Comments

[Александр Скуснов]

Один из вариантов - с помощью List Comprehension

[a+b+c | a  <- mas!!0, b <- mas!!1, c <- mas!!2]
[3,4,4,5,5,6,4,5,5,6,6,7]

[Александр Скуснов]

Вот моё решение для любого количества внутренних списков на Haskell:

mas = [[1,2], [1,2,3], [1,2]]
map sum . sequence $ mas   -- [3,4,4,5,5,6,4,5,5,6,6,7]

[Александр Скуснов]

Понял, что надо искать не все комбинации, а только те, которые дают в сумме 6. Тогда так:

import Control.Monad
do {lst <- sequence mas; guard (sum lst == 6); return lst}

-- [[1,3,2],[2,2,2],[2,3,1]]