find the all possible sum in a matrix

Question

I am trying to write a code that find the sum of all the possible numbers in a 2d matrix. But the catch is that you must choose one element from one row.

#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;
}

this code only brings out the sum of all the elements in the 2d array. So i need help trying to find all the possible sum given one element from each row is chosen for each sum.

2
1 1
1 2

2, 3, 2, 3

this should be the output but it only gives out 5

Voting to close this as an exact duplicate of your previous question: [Finding the Lowest sum in a 2d array by picking 1 element from each row](https://stackoverflow.com/questions/61453950/finding-the-lowest-sum-in-a-2d-array-by-picking-1-element-from-each-row) At least tell us why you're asking a new question. — Botje, Apr 28 '20 at 06:59
Why are you using plain old arrays instead of `std::vector>`? Why are you using Variable Length Arrays that are not part of the C++ standard (`int array[n][n]={0};`) and why are you attempting to initialize the VLA which is unsupported by any standard? See also [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/364696) Additionally, please do not post duplicate questions. — David C. Rankin, Apr 28 '20 at 07:04

score 0 · Accepted Answer · answered Apr 28 '20 at 07:16

Your core loop is all wrong. If you want sum[i] to contain the values for a given path, you need to treat i as if it were a path through the matrix.

In general, treat i as a number in base n (=2 for your example). That means

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

You can recover the various indexes by repeatedly dividing by n and taking the remainder:

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];
   }
}

And of course this trick only works if n*n < 2**64 (as uint64_t is 64 bits). For a more general approach see my answer to your other question.

find the all possible sum in a matrix

1 Answers1