Leetcode

Combination Sum IV

  • Time:O(|\texttt{coins}| \cdot \texttt{target})
  • Space:O(\texttt{target})

C++

class Solution {
 public:
  int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned long 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];
  }
};

JAVA

class Solution {
  public int combinationSum4(int[] nums, int target) {
    // dp[i] := # 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];
  }
}

Python

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)