Count ordered ways to reach a target

Question

Given distinct positive integers nums and a target, count the number of ordered sequences drawn from nums (with repetition) that sum to the target. Because order matters, 1+3 and 3+1 count as two different sequences. Return the count. Target O(	ext{target} 	imes \text{nums}).

Accepted Answer

Let dp[t] be the number of ordered sequences summing to t, with dp[0] = 1 (the empty sequence). Here the loop order is the mirror image of the "count combinations" problem: put the target amounts on the outside and the numbers on the inside. Fixing the last element of the sequence lets every ordering be counted: dp[t] = \sum{v \in 	ext{nums},\, v \le t} dp[t - v]. Tracing nums = [1, 2, 3], target = 4: dp[1] = 1, dp[2] = dp[1] + dp[0] = 2, dp[3] = dp[2] + dp[1] + dp[0] = 4, and dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7. That matches the seven sequences. Time O(	ext{target} 	imes \text{…

Count ordered ways to reach a target

Your answer

More Coding questions