153. Combination Sum - Count Combinations

Given n distinct positive integers (candidates, each usable an unlimited number of times) and a target, count the number of distinct combinations (as multisets - order doesn't create a new combination) of candidates that sum exactly to the target.

Input: The first line contains an integer n. The second line contains n space-separated distinct positive integers (the candidates). The third line contains the integer target. Output: Print a single integer - the number of distinct combinations (candidates reusable) that sum exactly to the target.

1 <= n <= 20, 1 <= target <= 100

The 'non-decreasing order' rule is the single most important detail here - forgetting it is the most common way to accidentally count the same combination multiple times in problems involving reusable, unordered picks.

Count how many distinct combinations of reusable candidate numbers add up to exactly a target, treating combinations as multisets (order doesn't matter). Brute force: Try every possible ORDERED sequence of candidate choices (allowing candidates to be picked in any order, not just non-decreasing) - this massively over-counts, since e.g. [2,2,3] and [2,3,2] and [3,2,2] would all be counted as separate sequences even though they represent the identical combination. Optimised: Restricting recursion to only ever pick candidates in NON-DECREASING order relative to the last pick (never revisiting an earlier candidate once you've moved past it) guarantees each distinct multiset combination is generated EXACTLY once - this ordering constraint is the entire trick that turns permutation-counting into combination-counting.

Maintain a single array dp[0..target] with dp[0] = 1, and for each candidate coin value c (processed in the outer loop), update dp[amt] += dp[amt - c] for amt from c up to target in increasing order. Iterating candidates in the outer loop and amounts in the inner loop ensures each combination is counted once regardless of the order its coins are used in, matching the required 'multiset' semantics. This computes exactly the same values as the memoized version but collapses the 2D memo table down to a single rolling 1D array, cutting the space from quadratic to linear. Time: O(n*target) Space: O(target)

Recursively try, for each candidate starting from the first, either using it again (reducing the remaining target by its value) or moving on to the next candidate permanently, counting a valid combination whenever the remaining target hits exactly zero. Considering candidates strictly in order (never going back to an earlier one once skipped) ensures each multiset is only counted once as a combination rather than once per ordering, but without caching, the same (candidate index, remaining target) subproblem gets recomputed repeatedly across different branches. Time: exponential Space: O(target)

Use the same recursion as brute force (at each candidate, either reuse it or move to the next one, with the same in-order rule to avoid double-counting), but cache the number of ways to complete a given (candidate index, remaining amount) pair the first time it is computed. Since there are only O(n * target) distinct such pairs, caching turns what would otherwise be an exponential number of recursive calls into a linear number of unique computations, each O(1) once its dependencies are known. Time: O(n*target) Space: O(n*target)

1. Recurse through the candidates in a FIXED order, deciding for each how many times (0 or more) to use it before moving to the next candidate. 2. At each candidate, either use it again (reducing the remaining target) or move on to the NEXT candidate in the fixed order - never go back to an earlier candidate. 3. Only ever considering candidates in non-decreasing order relative to the last one chosen is exactly what prevents counting the same multiset combination more than once.

Time: Exponential in the worst case, but heavily pruned by the ordering constraint and the target bound - manageable for the given constraints (target <= 100, n <= 20). Space: O(target / smallest candidate) for the recursion depth in the worst case.

Test n = 1 (only works if the single candidate evenly divides the target), a target unreachable by any combination (0), and n = 20 with target = 100 for performance.

Be ready to contrast this with the 'print all combinations' variant (which needs to actually build and print each list) versus this 'just count them' variant, which can sometimes be optimized further with DP if only the count (not the actual combinations) is needed.