найти всю возможную сумму в матрице

Question

Я пытаюсь написать код, который находит сумму всех возможных чисел в 2-мерной матрице. Но суть в том, что вы должны выбрать один элемент из одной строки.

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
#include <math.h>
using namespace std;
int main() { 
    int n;
    cin>>n;
    int array[n][n]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>array[i][j];
        }
    }
    int power=pow(n,n);
    int sum[power]={0};
    for(int i=0;i<power;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<n;l++){
                sum[i]=sum[i]+array[j][l];
            }
        }
    }
    for(int i=0;i<power;i++){
        cout<<sum[i]<<" ";
    }
    return 0;
}

, этот код только выдает сумму всех элементов в 2d массиве. Поэтому мне нужна помощь, пытаясь найти всю возможную сумму, если для каждой суммы выбран один элемент из каждой строки.

2
1 1
1 2

2, 3, 2, 3

это должен быть вывод, но он выдает только 5

Answer 1

Ваше ядро ​​l oop все не так. Если вы хотите, чтобы sum[i] содержал значения для данного пути, вам нужно трактовать i, как если бы это был путь через матрицу.

В общем, обрабатывать i как число в базе n (= 2 для вашего примера). Это означает, что

i = idx_1 * n ^ (n-1) + idx_2 * n ^ (n-2) + ... + idx_n

Вы можете восстановить различные индексы путем многократного деления на n и взятия остатка:

for(uint64_t i=0;i<power;i++){
   sum[i] = 0;
   uint64_t encoded_index = i;
   for (size_t j = 0; j < n; j++) {
       uint64_t index_j = encoded_index % n;
       encoded_index /= n;
       sum[i] += hist[j][index_j];
   }
}

И, конечно, этот трюк работает, только если n * n <2 ** 64 (так как uint64_t равен 64 битам). Для более общего подхода см. Мой ответ на ваш другой вопрос. </p>