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.