Combination Sum IV

Problem Description

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The test cases are generated so that the answer can fit in a 32-bit integer.

Key Insights

• Each number in nums can be used multiple times to form combinations.
• Different sequences of the same combination are considered distinct (e.g., (1, 1, 2) is different from (1, 2, 1)).
• The problem can be approached using dynamic programming to count combinations for each target value incrementally.

Space and Time Complexity

Time Complexity: O(target * n), where n is the number of elements in nums.
Space Complexity: O(target), as we can use a 1D array to store counts for each intermediate target.

Solution

The problem is solved using dynamic programming. We create an array dp where dp[i] represents the number of combinations that sum up to i. We initialize dp[0] to 1 (one way to reach zero: using no elements). For each number in nums, we iterate from that number to the target, updating our dp array to accumulate the counts of combinations.

Code Solutions