Optimizing Column Selection for Row-Wise Minimum Sum in Matrices

I have an issue finding an efficient solution for the following problem:

Given a rectangular matrix of integers with dimensions 𝑚×𝑛, select exactly 𝑄 columns and then, for each row in the matrix, choose a single element from the selected columns such that the total sum of the chosen elements is minimized.

Example:

Input:

𝑄 = 2 (You must select 2 columns)

Matrix:
[4 2 7]
[3 8 1]
[5 6 9]

Output: Selecting columns {1,2} gives the smallest total sum of 9.

I have tried progressively constructing combinations of columns from smaller to larger subsets. Starting with individual columns, I build combinations by adding one column at a time, ensuring that every combination of size 𝑄 is eventually generated.

For each combination, I compute the row-wise minimum of the selected columns and sum these values across all rows. To avoid redundant computations, I store intermediate results for smaller combinations and use them when building larger combinations.

My issue with this is it’s computationaly expensive for larger matrices and I’m looking for suggestions for more efficient solution if such solution exists.