组合总和4是否为背包问题？能否用背包+递归求解？

1. 组合总和4属于背包问题范畴吗？ #

完全属于，它是非常典型的排列型完全背包变体，是背包问题大类下的经典题型。
和你之前做对的分割等和子集做个对比就很清楚：

• 分割等和子集是标准01背包：每个数组元素只能选一次，判断能不能凑出指定和，不考虑选元素的顺序
• 组合总和4是特殊的完全背包：每个数组元素可以无限次重复选，要求统计凑出指定和的不同顺序的组合数（本质是统计排列数）

2. 能不能用背包+递归的思路解决这个问题？ #

完全可以——带备忘录的记忆化递归本质就是自顶向下实现的动态规划，本身就是背包类问题的标准解法之一。
你之前的代码跑不通，根本原因是直接照搬了01背包的递归框架，完全和这道题的规则不匹配，具体有两个硬伤：

• 递归转移逻辑完全错配：你之前的递归逻辑是“处理到第i个元素时，选/不选当前元素，之后直接把指针移到i+1”——这是01背包的核心逻辑，目的是保证每个元素只被考虑一次。但组合总和4允许元素无限次复用，还要统计不同顺序的路径，这种“选完就跳过当前元素”的逻辑，直接把所有需要重复选元素的路径、不同顺序的路径全部剪掉了，根本不可能算出正确结果。
• 核心参数缺失：你写的函数甚至没有把题目要求的目标值target作为入参，反而直接把数组所有元素的和当成递归的计算目标，从计算起点就和题目要求不对等。

正确的背包+递归实现思路 #

因为这道题不需要记录“当前处理到数组第几个元素”的状态，之前用的二维备忘录完全可以简化成一维：

• 状态定义：dp[tar]代表凑出目标和为tar的合法排列个数
• 递归边界：当tar === 0时返回1（找到1条合法路径）；当tar < 0时返回0（路径非法）
• 缓存命中：如果当前tar的结果已经存在备忘录里，直接返回缓存值
• 状态转移：遍历所有数组元素，只要元素值小于等于当前tar，就把“凑tar - 当前元素值的排列数”累加到当前结果里，再把结果写入备忘录。

示例代码如下：

var combinationSum4 = function(nums, target) {
    // 一维备忘录：dp[t] 存储和为t的排列数
    const memo = new Array(target + 1).fill(null);

    const dfs = (remain) => {
        if (remain === 0) return 1;
        if (remain < 0) return 0;
        if (memo[remain] !== null) return memo[remain];

        let count = 0;
        // 每次从头遍历所有元素，支持重复选取、不同顺序
        for (const num of nums) {
            if (num <= remain) {
                count += dfs(remain - num);
            }
        }
        memo[remain] = count;
        return count;
    }

    return dfs(target);
};

注：这个思路和经典的完全背包递推逻辑本质是一致的，只是从自底向上的递推改成了自顶向下的记忆化递归，核心状态和转移逻辑完全没有变化。

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