Search for unique combinations

A baseline tries every ordered sequence up to the target, sorts each successful sequence, and deduplicates the results. It repeatedly explores equivalent states: 2+2+3, 2+3+2, and 3+2+2 all consume the same capacity. Memoizing only remaining capacity also loses the information needed to enforce allowed candidate order.

Sort and deduplicate candidates. A state holds the remaining sum and the first candidate index allowed next. Choosing index i recurses with the same lower bound i, permitting reuse. Values exceeding the remainder prune all later values because the array is sorted. Emit a copy of the path only at remainder zero.

the path is nondecreasing, its sum plus remaining equals target, and every continuation uses an index at least the last choice. Every multiset has exactly one sorted representation, so it appears once. Positive values strictly decrease remaining, proving termination. The reference uses explicit frames and one mutable path, preserving recursive reasoning without a recursion-depth limit.

Let m be supplied candidates, k distinct candidates, D=floor(target/minimum), N explored prefix states, and B total output entries. Time is O(m + k log k + N + B), auxiliary space O(k + D), and output space O(B). A loose worst-case search bound is O((k + 1)^D); reporting only O(target × k) would confuse enumeration with a counting DP. Empty candidates are handled separately without a minimum. Very large outputs remain expensive.

Follow-up 1 — each distinct size may be selected once. Predict the example: [2,2,3] disappears and [7] remains. Move the lower bound to i+1 after selection. If repeated input entries represent separate inventory units, do not deduplicate; instead skip equal sibling choices while retaining their multiplicities.

Follow-up 2 — return the number only. Use DP with candidates outside and amounts inside the loops to count unordered combinations. Reversing loop order counts ordered sequences. Demonstrate the difference for target 3 with [1,2]: two combinations versus three sequences.

Senior depth derives canonical state and restoration. Lead depth defines result limits, pagination, and cancellation before exposing exponential enumeration.

Reference: solution.py (download file, source below); tests compare independent count-vector enumeration, verify duplicates/zero/impossible inputs, and exercise a deep path.

"""Enumerate unique nondecreasing combinations, with unlimited positive values."""


def combinations(candidates, target):
    if not isinstance(target, int) or target < 0:
        raise ValueError("nonnegative integer target required")
    unique = set()
    for value in candidates:
        if not isinstance(value, int) or value <= 0:
            raise ValueError("positive integer candidates required")
        unique.add(value)
    values = sorted(unique)
    result, path = [], []
    # Each frame holds the next candidate index and remaining target.
    stack = [[0, target]]
    while stack:
        index, remaining = stack[-1]
        if remaining == 0:
            result.append(path.copy())
            stack.pop()
            if stack:
                path.pop()
        elif index == len(values) or values[index] > remaining:
            stack.pop()
            if stack:
                path.pop()
        else:
            stack[-1][0] += 1
            path.append(values[index])
            stack.append([index, remaining - values[index]])
    return result

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/31-combination-search -p 'test_*.py'