LeetCode Entry

377. Combination Sum IV

9.09.2023 medium 2023 kotlin

Number of ways to sum up array nums to target

377. Combination Sum IV medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/334

Problem TLDR

Number of ways to sum up array nums to target

Intuition

This is a canonical DP knapsack problem: choose one of the items and decrease the target by its value. If target is zero - we have a single way, if negative - no ways, otherwise keep taking items. The result will only depend on the target, so can be cached.

Approach

In this code:

  • trick to make conversion 0 -> 1, negative -> 0: 1 - (t ushr 31), it shifts the leftmost bit to the right treating sign bit as a value bit, converting any negative number to 1 and positive to 0
  • IntArray used instead of Map using takeIf Kotlin operator

Complexity

  • Time complexity: \(O(n^2)\), n for the recursion depth, and n for the inner iteration

  • Space complexity: \(O(n^2)\)

Code


    fun combinationSum4(nums: IntArray, target: Int): Int {
      val cache = IntArray(target + 1) { -1 }
      fun dfs(t: Int): Int = if (t <= 0) 1 - (t ushr 31) else
        cache[t].takeIf { it >= 0 } ?:
        nums.sumBy { dfs(t - it) }.also { cache[t] = it }
      return dfs(target)
    }