求解给定面额凑指定金额组合数时遇Segmentation fault (signal 11)

嘿，我来帮你排查这个Segmentation Fault（信号11）的问题～你写的递归思路是对的，但漏掉了关键的终止条件，导致数组越界访问，触发了段错误。

先看一下你提供的代码：

#include<stdio.h>
int denomination(int amt,int coin[],int n){
    //int sum=0;
    if(amt==0){
        return 1;
    }
    else if(amt<0)return 0;
    else{
        int include=denomination(amt-coin[n-1],coin,n);
        int exclude=denomination(amt,coin,n-1);
        return include+exclude;
    }
}
int main() {
    // Insert your code here.
    int t,amt,n,coin[100];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&amt);
        int a=denomination(amt,coin,n);
        printf("%d\n",a);
    }
    return 0;
}

问题出在哪？ #

当递归过程中n逐渐减到0的时候，代码仍然会执行coin[n-1]，也就是访问coin[-1]——这属于非法访问数组的内存区域，直接触发了Segmentation Fault。而且当没有硬币可选（n=0）但金额还没凑完（amt>0）时，我们应该返回0，但你的代码没有处理这种情况。

修复后的代码 #

只需要在递归函数开头加上n <= 0的判断，就能避免数组越界：

#include<stdio.h>
int denomination(int amt, int coin[], int n){
    // 没有硬币可选且金额未凑完，直接返回0
    if(n <= 0 && amt > 0){
        return 0;
    }
    if(amt == 0){
        return 1;
    }
    else if(amt < 0){
        return 0;
    }
    else{
        int include = denomination(amt - coin[n-1], coin, n);
        int exclude = denomination(amt, coin, n-1);
        return include + exclude;
    }
}
int main() {
    int t, amt, n, coin[100];
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &coin[i]);
    }
    scanf("%d", &t);
    while(t--){
        scanf("%d", &amt);
        int a = denomination(amt, coin, n);
        printf("%d\n", a);
    }
    return 0;
}

额外优化：避免重复计算（可选） #

这个递归实现会有很多重复计算的情况，比如同一个amt和n的组合会被多次递归调用。如果要处理较大的金额或更多硬币种类，推荐用**记忆化搜索（动态规划的一种）**来优化，把已经计算过的结果存起来，避免重复计算：

#include<stdio.h>
#include<stdlib.h>

// 记忆化数组，存储已计算的(amt, n)对应的组合数
int** memo;

int denomination(int amt, int coin[], int n){
    if(n <= 0 && amt > 0){
        return 0;
    }
    if(amt == 0){
        return 1;
    }
    else if(amt < 0){
        return 0;
    }
    // 如果已经计算过，直接返回存储的结果
    if(memo[amt][n] != -1){
        return memo[amt][n];
    }
    int include = denomination(amt - coin[n-1], coin, n);
    int exclude = denomination(amt, coin, n-1);
    // 保存计算结果到记忆化数组
    memo[amt][n] = include + exclude;
    return memo[amt][n];
}

int main() {
    int t, max_amt = 0, n, coin[100];
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &coin[i]);
    }
    scanf("%d", &t);
    
    // 先读取所有测试金额，找出最大值来初始化记忆化数组
    int* amts = (int*)malloc(t * sizeof(int));
    for(int i=0; i<t; i++){
        scanf("%d", &amts[i]);
        if(amts[i] > max_amt){
            max_amt = amts[i];
        }
    }
    
    // 初始化记忆化数组，所有值设为-1表示未计算
    memo = (int**)malloc((max_amt + 1) * sizeof(int*));
    for(int i=0; i<=max_amt; i++){
        memo[i] = (int*)malloc((n + 1) * sizeof(int));
        for(int j=0; j<=n; j++){
            memo[i][j] = -1;
        }
    }
    
    // 处理每个测试用例
    for(int i=0; i<t; i++){
        int amt = amts[i];
        int a = denomination(amt, coin, n);
        printf("%d\n", a);
    }
    
    // 释放内存，避免内存泄漏
    for(int i=0; i<=max_amt; i++){
        free(memo[i]);
    }
    free(memo);
    free(amts);
    
    return 0;
}

内容的提问来源于stack exchange，提问作者Ayush Gupta