Combination Sum Iv - JS Solution

JS
Editorial

Approach

Approach (Bottom-Up Dynamic Programming — Building from Smaller Targets)

This problem asks for the number of ordered combinations of numbers from nums that sum to a given target. We solve it using a bottom-up dynamic programming (DP) approach that reuses previously computed subresults to build up solutions for larger targets.

  • State definition: dp[i] represents the number of distinct ordered combinations that sum to i.
  • Base case: dp[0] = 1 — there is exactly one way to form sum 0 (by choosing no numbers).
  • Sorting step: Before the DP starts, we sort nums in ascending order. This enables an early termination inside the inner loop: once a number num exceeds the current target i, all following numbers (being larger) would also exceed i — meaning none of them can contribute to forming i. Since all numbers are positive, adding any larger number would only increase the sum, never reduce it. Therefore, we can safely break out of the loop to avoid unnecessary checks.
  • Processing order: We fill the dp table from smaller to larger targets, ensuring subproblems (dp[i - num]) are computed before they are needed. This is possible because all numbers in nums are positive, ensuring that subproblems always correspond to smaller targets.
  • Transition logic: For each target i from 1 to target:
    • Iterate over each number num in nums.
    • If num > i, stop checking further — since the array is sorted, all remaining numbers will also be too large to contribute.
    • If num ≤ i, we can append num to every combination that sums to i - num, effectively unlocking dp[i - num] new ways to reach i.
    • Thus, we update dp[i] += dp[i - num].
  • Result: After building the entire table, dp[target] gives the total number of combinations that sum to the target.

Time Complexity

Let n = nums.length and T = target.

Sorting step:
We first sort the array nums in ascending order, which takes O(n log n) time. This sorting enables an early termination optimization in the inner loop: once a number num exceeds the current target i, all subsequent numbers (being larger) can be safely skipped.

DP iteration phase:
We build the DP table for every target i from 1 to T, checking each of the n numbers in nums for contribution. In the worst case — whether nums is sorted or not — every number must be considered for each target, leading to O(T × n) operations. Sorting affects only the average case (by allowing early exits), but does not change the asymptotic bound.

Therefore:

  • With sorting (for early termination): O(T × n + n log n)
  • Without sorting: O(T × n)

T is typically much larger than log n given the constraints of this problem. Therefore, the O(T × n) term usually dominates the cost of sorting. In practice, the time saved from early termination after sorting often outweighs the O(n log n) cost of sorting, making sorting beneficial in the average case. However, whether to sort should ultimately depend on the specific constraints and performance preferences.

Space Complexity

Let T = target.

DP array:
The algorithm maintains a one-dimensional array dp of length T + 1, where each entry dp[i] stores the number of ways to form the sum i. This contributes O(T) space.

Overall:
The total additional space used by the algorithm is O(T).