🌕 🌗 377. 组合总和 Ⅳ

难度: 🌕 🌗

• 问题描述
• 解法
• 输出
• 进阶

问题描述

---

解法

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 思路：
        // 背景 - 所有元素各不相同
        // 完全背包问题 - 组合
        int len = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 0; i <= target; i ++) {
            // 要求总和，需要遍历所有物品，看是否满足要求得到 总和 = i
            for(int j = 0; j < len; j ++) {
                if(i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

---

输出

---

进阶

• 假设组合中存在某正数 x & 某负数 y
• 则必存在 a, b 使得 ax + by = 0
• 假设组合中一个解为 {m, n, k} 满足 sum = target
• 则 {m, n, k, a 个 x, b 个 y} 也必然满足条件
• 同理，{m, n, k, 2a 个 x, 2b 个 y} 也必然满足条件
• 即，解有无穷个
• 此时需要限制解集的大小，否则永远也无法穷尽所有情况