Добрый день. Есть задача написать процедуру на вход которой будет подаваться двумерный массив рандомной размерности. Требуется вывести все возможные суммы элементов с условием что за одну итерацию из одномерного массива(строки) берется только одно значение. Сам алгоритм выглядит следующим образом. 

Пример:

на входе:
123
456
789

на выходе:
1+4+7 1+4+8 1+4+9
1+5+7 1+5+8 1+5+9
1+6+7 1+6+8 1+6+9

2+4+7 2+4+8 2+4+9
2+5+7 2+5+8 2+5+9
2+6+7 2+6+8 2+6+9

3+4+7 3+4+8 3+4+9
3+5+7 3+5+8 3+5+9
3+6+7 3+6+8 3+6+9

Вопрос: как реализовать данный алгоритм для массива nxn(array [n][n])?

Стек + Рекурсия.
В стеке лежат выбранные элементы предыдущих строк массива.
В рекурсивной функции цикл по текущей стоке, помещение выбранного элемента в стек, рекурсивный вызов для следующей строки или вывод результата.
Учти, что каждая строка может иметь свою разменость:
Например, Вход:
1 2
3 4 5
6 7 8 9

Использование рекурсии применительно к данным неизвестной размерности приводит к переполнению стека, как правило.

Ну можно обойтись без рекурсии, если складывать все необходимые данные стек (я имею ввиду java.util.Stack). Будет хитровывернутый цикл, с continue и break, для начала надо написать с рекурсией, а затем оптимизировать.

Кстати, пришёл в голову очень простой способ получить желаемое:


Правда очень много делений. Можно сделать используя только сложение, но тогда понадобится доп array[n] памяти

Но не n*n, а n в степени n.