使用 oh-my-zsh

377、组合总和

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

进阶：

• 如果给定的数组中含有负数会怎么样？
• 问题会产生什么变化？
• 我们需要在题目中添加什么限制来允许负数的出现？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

组合数内有不同的数字有顺序区分

组合内的数字要小于等于目标值。

可以自下向上求解，1～n,n的个数依赖于n-1的组合数

1、暴力递归

• 代码

// java
class Solution {
    int i = 0;

    public int combinationSum4(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }
        combinationSum4(nums, 0, target);
        return i;
    }

    public void combinationSum4(int[] nums, int beforeRe, int target) {
        // 超过了目标值
        if (beforeRe > target) {
            return;
        }
        // 找到了，退出
        if (beforeRe == target) {
            i++;
            return;
        }
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // 计算当前值
            int tempRe = beforeRe + nums[i];
            // 递归
            combinationSum4(nums, tempRe, target);
        }
    }

// 作者：niu-you-rou
// 链接：https://leetcode-cn.com/problems/combination-sum-iv/solution/di-gui-dao-fen-zhi-dao-dong-tai-gui-hua-by-niu-you/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

2、记忆化递归

// C++
class Solution {

    public int combinationSum4II(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        // 缓存中间结果
        Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
        return combinationSum4II(nums, target, length, cache);
    }

    public int combinationSum4II(int[] nums, int target, int length, Map<Integer, Integer> cache) {
        if (target < 0) {
            return 0;
        }
        if (target == 0) {
            return 1;
        }
        Set s = cache.keySet();
        // 中间结果已求得，直接返回
        if (s.contains(target)) {
            return cache.get(target);
        }
        int temp = 0;
        for (int i = 0; i < length; i++) {
            // 自顶向下，更新缩减目标值
            temp += combinationSum4II(nums, target - nums[i], length, cache);
        }
        cache.put(target, temp);
        return temp;
    }

// 作者：niu-you-rou
// 链接：https://leetcode-cn.com/problems/combination-sum-iv/solution/di-gui-dao-fen-zhi-dao-dong-tai-gui-hua-by-niu-you/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

动态规划

class Solution {
    public final int combinationSum4(int[] nums, int target) {
        // 临界情况处理
        if(nums==null){return 0;}
        int length=nums.length;
        // 状态数组，cache[i]表示和为i的组合的个数
        int[] cache=new int[target+1];
        cache[0]=1;
        // 自下而上，状态处理
        for(int i=1;i <= target;i++){
            int temp=0;
            // 求解每一个i的组合数
            for(int j=0;j<length;j++){
                // 找完了，继续下一轮循环
                if(i-nums[j]==0){
                    temp++;
                    continue;
                }
                if(i-nums[j]>0){
                    // 利用之前已经求得的组合数
                    temp += cache[i-nums[j]];
                }
            }
            // 缓存和为i的组合的个数
            cache[i]=temp;
        }
        return cache[target];
    }
}
// 作者：niu-you-rou
// 链接：https://leetcode-cn.com/problems/combination-sum-iv/solution/di-gui-dao-fen-zhi-dao-dong-tai-gui-hua-by-niu-you/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 另一个实现，代码更精炼

public class Solution {

    /**
     * 这里状态定义就是题目要求的，并不难，状态转移方程要动点脑子，也不难：
     * 状态转移方程：dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + ... （当 [] 里面的数 >= 0）
     * 特别注意：dp[0] = 1，表示，如果那个硬币的面值刚刚好等于需要凑出的价值，这个就成为 1 种组合方案
     * 再举一个具体的例子：nums=[1, 3, 4], target=7;
     * dp[7] = dp[6] + dp[4] + dp[3]
     * 即：7 的组合数可以由三部分组成，1 和 dp[6]，3 和 dp[4], 4 和dp[3];
    
     */
    public int combinationSum4(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[target + 1];

        // 注意：理解这一句代码的含义
        // 处理i == nums[j] 的情况
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < len; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

// 作者：liweiwei1419
// 链接：https://leetcode-cn.com/problems/combination-sum-iv/solution/dong-tai-gui-hua-python-dai-ma-by-liweiwei1419/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com