c++ - 如何找到递归函数中的错误？

Question

我试图找到给定2D数组NxN的每个可能排列的每一列的最大和最小的最小值，其中每一行中的值都可以向左移动。例如，数组

4 6 
3 7

将有4种可能的排列:

4 6   6 4   4 6    6 4
3 7   3 7   7 3    7 3

每个排列的最大和分别为13、11、11、13。因此，最大和最小的为11。我编写了一个应该起作用的递归函数，但由于某种原因，它仅对较小的数组起作用比6x6 ...我是编程 Realm 的新手，最近才了解有关递归的知识，对于任何关于递归思考和调试代码的帮助或建议将不胜感激...
对于阵列4x4

7410 1371 2665 3195
4775 4130 6499 3414
300 2092 4009 7638
5351 210 7225 7207

答案是18349，我的代码为我提供了正确的答案。
但是，对于阵列6x6

5219 842 7793 2098 5109 2621
1372 3253 3804 5652 810 1620
4894 6792 1784 4335 4772 6656
3203 1070 4716 5335 1157 6855
5529 2767 2205 408 7516 7454
375 7036 2597 5288 937 2893

答案应该是23733，但我有24176。这怎么可能？
这是我的代码:

#include <iostream>
using namespace std;

#define MAX_N 1000

int n, matrix[MAX_N][MAX_N], shift[MAX_N] = {0}, minSum = 100000000;

void possibTree(int position){
    
    //Base case
    if(position == n){
        for (int i = 0; i < n; i++) {
            // Temporary array to store the values in the row that just shifted towards the left
            int temp[MAX_N] = {0};
            for (int j = 0; j < n; j++) {
                if(j - shift[i] < 0)
                    temp[n+(j-shift[i])] = matrix[i][j];
                else
                    temp[j-shift[i]] = matrix[i][j];
            }
            for (int k = 0; k < n; k++)
                matrix[i][k] = temp[k];
        }
        
        int max = 0;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                temp += matrix[j][i];
            }
            if(temp > max)
                max = temp;
        }
        if(minSum > max)
            minSum = max;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        shift[position] = i;
        possibTree(position+1);
    }
    return;
}

int main() {
    while(cin >> n){
        memset(matrix, 0, sizeof(matrix));
        memset(shift, 0, sizeof(shift));
        if(n == -1) // The user enters "-1" to end the loop and terminate the program.
            return 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> matrix[i][j];
            }
        }
        possibTree(0);
        cout << minSum << endl;
        minSum = 100000000;
    }
    return 0;
}

Answer 1

好的，我相信我理解我的错误，我必须在每个基本案例的末尾将矩阵重置为其原始状态，当矩阵很小时，代码仍然能够找到所有可能的最大和，但是当矩阵得到更大的一些可能性没有产生。这是我的代码:

#include <iostream>
using namespace std;

#define MAX_N 1000

int n, matrix[MAX_N][MAX_N], OrigMatrix[MAX_N][MAX_N], shift[MAX_N] = {0}, minSum = 100000000;

void possibTree(int position){
    
    //Base case
    if(position == n){
        for (int i = 0; i < n; i++) {
            // Temporary array to store the values in the row that just shifted towards the left
            int temp[MAX_N] = {0};
            for (int j = 0; j < n; j++) {
                if(j - shift[i] < 0)
                    temp[n+(j-shift[i])] = matrix[i][j];
                else
                    temp[j-shift[i]] = matrix[i][j];
            }
            for (int k = 0; k < n; k++)
                matrix[i][k] = temp[k];
        }
        
        int max = 0;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                temp += matrix[j][i];
            }
            if(temp > max)
                max = temp;
        }
        if(minSum > max)
            minSum = max;
        //EDITS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = OrigMatrix[i][j];
            }
        }
        return;
    }
    
    for (int i = 0; i < n; i++) {
        shift[position] = i;
        possibTree(position+1);
    }
    
    return;
}

int main() {
    while(cin >> n){
        memset(matrix, 0, sizeof(matrix));
        memset(shift, 0, sizeof(shift));
        if(n == -1) // The user enters "-1" to end the loop and terminate the program.
            return 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> matrix[i][j];
            }
        }
        //EDITS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                OrigMatrix[i][j] = matrix[i][j];
            }
        }
        possibTree(0);
        
        cout << minSum << endl;
        minSum = 100000000;
    }
    return 0;
}