Combination Sum IV

Combination Sum IV is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Coin Change / Unbounded Knapsack Style) subpattern.

Problem statement

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.

Example 1:

Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3 Output: 0

Constraints:

- 1 <= nums.length <= 200

- 1 <= nums[i] <= 1000

- All the elements of nums are unique.

- 1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Topics and companies

Topics: Array, Dynamic Programming.

Reported in interviews at Bloomberg, Wish, Apple.

How to practise Combination Sum IV on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn + n * t), t is the value of target. time and O(t) space.

Open Combination Sum IV in the code editor, or read the Combination Sum IV editorial for a worked solution with its approach and complexity analysis.

Where Combination Sum IV sits in the DSA pattern sheet

Problems related to Combination Sum IV

Other problems that use the same 1D Array (Coin Change / Unbounded Knapsack Style) and Dynamic Programming (DP) Patterns techniques:

Opening the problem

Progress is saved as you study.