本地运行正常但LeetCode报signed int溢出的C++代码问题求助

题目信息 #

题目：组合总和 IV
描述：给定由不同整数组成的数组nums和目标整数target，返回相加等于target的可能组合数。测试用例确保答案可放入32-bit整数中。

用户代码 #

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i){
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

报错信息 #

• 报错位置：第9行第27列
• 错误内容：运行时错误：有符号整数溢出：2147483647 + 1无法用int类型表示
• 摘要：UndefinedBehaviorSanitizer: undefined-behavior solution.cpp:9:27
• 补充：本地运行无异常，但在线提交触发该错误

问题原因与解决方法 #

问题出在动态规划的累加过程中：虽然题目保证最终答案能放入32位int，但计算中间步骤时，dp[i]的累加值可能超过int的最大值（2^31-1），触发有符号整数溢出的未定义行为。本地环境可能未开启严格的溢出检查所以没报错，而在线OJ的UndefinedBehaviorSanitizer会检测到这种情况。

解决方法1：改用无符号整数存储DP数组 #

将vector<int>改为vector<unsigned int>，无符号整数的溢出是定义良好的（模2^32），且题目保证最终结果在32位int范围内，最后转成int即可：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i){
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return static_cast<int>(dp[target]);
    }
};

解决方法2：添加溢出检查 #

在累加前判断当前dp[i]加上dp[i-num]是否会超过int最大值，仅当安全时才执行加法：

#include <climits>

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i){
            for (int num : nums) {
                if (i >= num && dp[i] <= INT_MAX - dp[i - num]) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

内容的提问来源于stack exchange，提问作者Vũ Đức Trung