Skip to content

377. Combination Sum IV 👍

  • Time: $O(|\texttt{coins}| \cdot \texttt{target})$
  • Space: $O(\texttt{target})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned long> dp(target + 1);
    dp[0] = 1;

    for (int i = 1; i <= target; ++i)
      for (const int num : nums)
        if (i >= num)
          dp[i] += dp[i - num];

    return dp[target];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int combinationSum4(int[] nums, int target) {
    // dp[i] := the number of combinations that add up to i
    int[] dp = new int[target + 1];
    dp[0] = 1;

    for (int i = 0; i <= target; ++i)
      for (final int num : nums)
        if (i >= num)
          dp[i] += dp[i - num];

    return dp[target];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def combinationSum4(self, nums: list[int], target: int) -> int:
    dp = [1] + [-1] * target

    def dfs(target: int) -> int:
      if target < 0:
        return 0
      if dp[target] != -1:
        return dp[target]

      dp[target] = sum(dfs(target - num) for num in nums)
      return dp[target]

    return dfs(target)