c - 在算法上需要帮助(堆栈溢出)

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
这是我朋友给我的一个挑战我已经设法想出了一个递归算法，可以很好地处理小输入，但是我得到了大值的分割错误我想那是因为堆栈溢出。我用C语言来解决这个问题。
给你一个n个数字的数组。查找和打印子集的最大长度，使得对于该子集的任何两个数字，数字的总和不能被K整除。
输入在第一行包含2个数字n和k，在下一行包含n个数字a[i]，以便：

1 <= n <= 10^5
0 <= a[i] <= 10^9
1 <= k <= 100

# Example input:
4 3
1 7 4 2

# Output:
3

说明：(1 7 4) 1 + 7 = 8; 1 + 4 = 5; 7 + 4 = 11;它们都不能被3整除。
我的解决方案基于以下思想：对于数组中的所有数字，如果其可被k整除，则将其与其他数字的和进行检查。如果找到匹配项，则创建两个数组，一个排除和的第一项，另一个排除第二项，这样我们就从子集中排除了这些对然后对第一个数组做同样的处理如果我们检查了数组中的所有元素，然后将解决方案设置为数组的长度，并继续将“解算器”仅应用于长度大于已找到的解决方案的数组该算法在n

#include <stdio.h>

int n, k;

int * deleteElement(int * a, int n, int j){
    int *c = (int*) malloc((n-1) * sizeof(int));
    int k = 0;
    for(int i = 0; i < n; i++){
        if(i == j) continue;
        c[k] = a[i];
        k++;
    }
    return c;
}

int sol = 0;

void solver(int *a, int n, int *sol){
    int *b, *c;
    if(n <= *sol) return;
    for(int i = 0; i <  n-1; i++){
        for(int j = i + 1; j < n; j++){
             if((a[i] + a[j]) % k == 0){
                  c = deleteElement(a, n, i);
                  b = deleteElement(a, n, j);
                  solver(c, n-1, sol);
                  solver(b, n-1, sol);
                  return;
             }
         }
     }
     *sol = n;
}

int main(){
    scanf("%d", &n);
    scanf("%d", &k);
    int a[n];
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    solver(a, n, &sol);
    printf("%d\n", sol);
    return 0;
}

最佳答案

您可以使用迭代来删除两个递归调用中的一个，但这对堆栈空间没有帮助，因为它们具有相同的深度——一个调用与2一样糟糕。
编写一个完全迭代的算法来测试所有有效的集合是很容易的，但是这仍然是一个指数时间算法无论如何，这样做可以避免堆栈溢出，但运行时间太长因为那个算法也很糟糕，我不想写它。
解决此问题的合理线性时间方法是：
计算一个map modcounts，其中modcounts[m]=元素x的数量，这样x%k==m
由于任何有效子集只能有一个元素可被k整除，如果modcounts[0]>1，则设置modcounts[0]=1
类似地，如果k是偶数，modcounts[k/2]>1，那么将modcounts[k/2]=1
现在，将modcounts中的所有值相加，但如果：
i>0，i*2i*2>k和MODCOUNTS[i]规则4反映了这样一个事实：对于规则2和规则3中没有考虑到的情况，有效子集不能包含任何元素x和y（x+y）%k=0。最大的有效子集包括MODCOUNTS[i]中的所有元素，或MODCOUNTS[k-i]中的所有元素，但不包括两者的元素。
如果使用像哈希表这样的稀疏数据结构来实现MODCOUNTS，那么整个过程需要O（N）时间。