Combination Sum IV

Given distinct positive integers and a target, return how many ordered sequences of those numbers (repeats allowed) add up to the target.

A way to picture it

You're building a playlist that must last exactly target minutes from songs of a few lengths — repeats allowed, and order matters. Pick the last song; whatever plays before it is a shorter playlist you've already counted.

How to approach it

ways(t) = sum over each number x ≤ t of ways(t − x), with ways(0) = 1. Looping over t on the outside counts every order separately.

Example

Input: {"nums":[1,2,3],"target":4}. Output: 7.

Complexity: O(target · n) time and O(target) space. Each total tries every number once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.