LeetCode: 377. 组合总和 Ⅳ

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

377. 组合总和 Ⅳ

LeetCode - 377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路分析

起初，我以为是深度优先遍历或者回溯。要去验证的时候，发现，这是组合问题，没办法加备忘录。看答案，竟然是 Unbounded Knapsack 完全背包。

在以往的思维定式中，爬楼梯总是: \(f(i)=f(i−1)+f(i−2)\)。这道题突破了这个思维定式，爬楼梯也可以：\(f(i) = \sum\limits_{j=0}^{n-1}{f(i-nums[j])}\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-07-26 22:19:09
 */
public int combinationSum4(int[] nums, int target) {
  int[] dp = new int[target + 1];
  dp[0] = 1;
  for (int i = 1; i <= target; i++) {
    for (int j = 0; j < nums.length; j++) {
      if (i >= nums[j]) {
        dp[i] += dp[i - nums[j]];
      }
    }
  }
  return dp[target];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 暴力破解（8/17）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-02 14:55:07
 */
public int combinationSum4(int[] nums, int target) {
  Arrays.sort(nums);
  List<List<Integer>> result = dfs(nums, target);
  return result.size();
}

private List<List<Integer>> dfs(int[] nums, int target) {
  if (target < 0) {
    return null;
  }
  List<List<Integer>> result = new ArrayList<>();
  for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    if (num > target) {
      break;
    }
    if (num == target) {
      result.add(new ArrayList<>(List.of(target)));
      break;
    }
    List<List<Integer>> list = dfs(nums, target - num);
    if (list != null) {
      for (List<Integer> c : list) {
        c.add(num);
      }
      result.addAll(list);
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 暴力破解（8/17）→ 备忘录（8/17，超过空间限制）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-02 15:59:49
 */
public int combinationSum4(int[] nums, int target) {
  Arrays.sort(nums);
  Map<Integer, List<List<Integer>>> memo = new HashMap<>();
  List<List<Integer>> result = dfs(nums, target, memo);
  return result.size();
}

private List<List<Integer>> dfs(int[] nums, int target,
                                Map<Integer, List<List<Integer>>> memo) {
  if (target < 0) {
    return null;
  }
  if (memo.containsKey(target)) {
    return memo.get(target);
  }
  List<List<Integer>> result = new ArrayList<>();
  for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    if (num > target) {
      break;
    }
    if (num == target) {
      result.add(new ArrayList<>(List.of(target)));
      break;
    }
    List<List<Integer>> list = dfs(nums, target - num, memo);
    if (list != null) {
      for (List<Integer> c : list) {
        c.add(num);
      }
      result.addAll(list);
    }
  }
  memo.put(target, result);
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 原始方案走不通，加备忘录会内存🇰超限。看题解，改成爬楼梯解法。
 * <p>
 * 暴力破解（10/17）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-02 16:14:56
 */
public int combinationSum4(int[] nums, int target) {
  Arrays.sort(nums);
  return dfs(nums, target);
}

private int dfs(int[] nums, int target) {
  if (target == 0) {
    return 1;
  }
  int result = 0;
  for (int num : nums) {
    if (num > target) {
      break;
    }
    result += dfs(nums, target - num);
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 原始方案走不通，加备忘录会内存🇰超限。看题解，改成爬楼梯解法。
 * <p>
 * 暴力破解（10/17）-> 备忘录（6.27%）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-02 16:17:16
 */
public int combinationSum4(int[] nums, int target) {
  int[] memo = new int[target + 1];
  Arrays.fill(memo, -1);
  Arrays.sort(nums);
  return dfs(nums, target, memo);
}

private int dfs(int[] nums, int target, int[] memo) {
  if (target == 0) {
    return 1;
  }
  if (memo[target] >= 0) {
    return memo[target];
  }
  int result = 0;
  for (int num : nums) {
    if (num > target) {
      break;
    }
    result += dfs(nums, target - num, memo);
  }
  memo[target] = result;
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 原始方案走不通，加备忘录会内存🇰超限。看题解，改成爬楼梯解法。
 * <p>
 * 暴力破解（10/17）-> 备忘录（6.27%）-> 动态规划（4.73%）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-02 16:20:32
 */
public int combinationSum4(int[] nums, int target) {
  Arrays.sort(nums);
  int[] dp = new int[target + 1];
  dp[0] = 1;
  for (int i = 0; i <= target; i++) {
    for (int num : nums) {
      if (num + i > target) {
        break;
      }
      dp[i + num] += dp[i];
    }
  }
  return dp[target];
}

LeetCode: 377. 组合总和 Ⅳ

友情支持

377. 组合总和 Ⅳ

思路分析

参考资料