Minimum Canisters to Top Up an Exact Target

Problem Statement

An off-grid vacation rental property relies on a backup fuel tank that must be topped up to an exact target volume. You are given a list of unique positive integers canisters, where each entry represents the capacity of a specific reusable canister size available in an unlimited supply. You are also given an integer target, representing the exact volume of fuel required.

Write a function min_canisters_to_target that determines the combination containing the minimum number of canisters needed to top up the tank to exactly target.

• If multiple valid combinations tie for the minimum number of canisters, you may return any one of them.
• If it is impossible to reach the exact target volume using any combination of the provided canisters, return None.
• If target == 0, return an empty list [].

Function Signature

def min_canisters_to_target(canisters: list[int], target: int) -> list[int] | None:
    pass

Examples

Example 1

Input: canisters = [1, 5, 10, 25], target = 30
Output: [25, 5]  # or [10, 10, 10]
Explanation: 30 can be formed using 2 canisters (25 + 5) or 3 canisters (10 + 10 + 10). The minimum number of canisters is 2.

Example 2

Input: canisters = [2], target = 3
Output: None
Explanation: It is impossible to achieve an odd target of 3 using only canisters of size 2.

Example 3

Input: canisters = [4, 6, 9], target = 15
Output: [9, 6]
Explanation: 9 + 6 = 15 uses 2 canisters, which is optimal.

Constraints

• 1 <= len(canisters) <= 50
• 1 <= canisters[i] <= 10^4
• All elements in canisters are distinct positive integers.
• 0 <= target <= 10^4

Edge Cases to Consider

• target = 0: Should immediately return [].
• Single canister size that does not divide target: Should return None.
• Canisters sorted in non-optimal order: Greedy selection (taking the largest canister first) does not always yield the minimum count (e.g., canisters = [9, 6, 1], target = 12 yields [6, 6] with 2 canisters, whereas greedy takes 9 + 1 + 1 + 1 with 4 canisters).