K Sum三类场景下带K个数约束的动态规划实现疑问

问题结论 #

1. 新增选取K个数的约束不能直接统一在最外层加for(int k = 1; k <= K; k++)循环，三类场景的循环顺序需要匹配对应背包模型的遍历逻辑，K层循环的位置也要对应调整。
2. 你给出的代码（元素遍历在外层、和i正序遍历、K层循环在最内层）仅适配case2，不适配case1和case3。

详细解释 #

我们先明确三类场景对应的背包模型本质：

• case1：有序可重复选取 → 统计排列数的完全背包
• case2：无序可重复选取 → 统计组合数的完全背包
• case3：无序不可重复选取 → 统计组合数的01背包

你给出的代码适配性说明

你写的代码将元素遍历n放在最外层，i正序遍历，本质是完全背包的组合数统计逻辑，刚好匹配case2的要求，跑示例vec = {1,2,3}, target = 5, K = 3时会返回正确结果2。

• 不适配case1：因为元素遍历在外层，不会统计不同排列的解，同样的元素组合只会被算一次，跑示例只会返回2，无法得到case1要求的6个有序解。
• 不适配case3：因为i是正序遍历，允许同一个元素被多次选取，不符合不可重复的要求，跑示例返回2，无法得到case3要求的0。

三类场景带K约束的正确实现 #

case1（有序可重复，顺序不同算不同解）

对应排列数完全背包逻辑，遍历顺序为：先遍历K层，再遍历和i，最后遍历元素：

int KSumCase1(vector<int>& vec, int target, int K) {
    vector<vector<int>> dp(K+1, vector<int>(target+1, 0));
    dp[0][0] = 1;
    for (int k = 1; k <= K; k++) {
        for (int i = 1; i <= target; i++) {
            for (int n = 0; n < vec.size(); n++) {
                if (i >= vec[n]) {
                    dp[k][i] += dp[k-1][i - vec[n]];
                }
            }
        }
    }
    return dp[K][target];
}

case2（无序可重复，顺序不同算相同解）

就是你给出的实现，对应组合数完全背包逻辑：

int KSumCase2(vector<int> vec, int target, int K) {
    vector<vector<int>> dp(K+1,vector<int>(target + 1,0));
    dp[0][0] = 1;
    for (int n = 0; n < vec.size(); n++)
        for (int i = 1; i <= target; ++i)
            for (int k = 1; k <= K; k++)
            {
                if (i >= vec[n]) dp[k][i] += dp[k - 1][i - vec[n]];
            }
    return dp[K][target];
}

case3（无序不可重复，顺序不同算相同解）

对应01背包逻辑，仅需要把case2的i遍历改成倒序即可：

int KSumCase3(vector<int> vec, int target, int K) {
    vector<vector<int>> dp(K+1,vector<int>(target + 1,0));
    dp[0][0] = 1;
    for (int n = 0; n < vec.size(); n++)
        // i倒序遍历，避免同一个元素被多次选取
        for (int i = target; i >= vec[n]; --i)
            for (int k = 1; k <= K; k++)
            {
                dp[k][i] += dp[k - 1][i - vec[n]];
            }
    return dp[K][target];
}

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