N—E—E
2021-12-01 22:27
采纳率: 61.1%
浏览 29

这个组合总和问题哪里错了

问题遇到的现象和发生背景

题目:

img

问题相关代码,请勿粘贴截图
#include <stdio.h>
#include <string.h>

int result[10];
int CurrentNum = 0;

int ValidSize(){
    int size = 0;
    for (int i = 1; i <= 9; i++)
    {
        if (result[i]) size++;
    }
    //printf("the size now is %d\n",size);
    return size;
}

int Sum(){
    int sum;
    for (int i = 1; i < 10; i++)
    {
        if (result[i]) sum += result[i];
    }
    //printf("the sum now is %d\n",sum);
    return sum;
}

void CombineSum(int k,int n,int start){
    if (ValidSize() == k && Sum() == n)
    {
        for (int t = 1; t <= k; t++)
        {
            printf("%d",result[t]);
        }
        printf("\n");
        return;
    }
    for (int i = start; (k - ValidSize() < 9-i+1) && Sum() < n; i++)
    {
        result[++CurrentNum] = i;
        CombineSum(k,n,i+1);
        result[CurrentNum--] = 0;
    }
}

int main()
{
    int n,k;
    memset(result,0,sizeof(result));
    scanf("%d %d",&k,&n);
    CombineSum(k,n,1);
    system("pause");
    return 0;
}


运行结果及报错内容

没有输出,不知道为什么

img

这是加了两条调试语句的输出:

img

我的解答思路和尝试过的方法

不知道是不是for循环剪枝那里出问题了?还是sum函数有问题(输出的sum和回溯算法模拟的不一样)?

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

相关推荐 更多相似问题