Generate constrained NFT metadata
Overview
This question evaluates skills in combinatorial generation, constraint satisfaction, uniqueness enforcement, and reasoning about appropriate data structures, algorithms, and time/space complexity for producing constrained NFT metadata.
Given a set of trait types (e.g., background, eyes, hat), each with a list of allowed values, and a target count N, implement a function to generate N NFT metadata items. Support follow-up constraints such as: (a) no repeated value for a trait within a single NFT; (b) uniqueness of the full trait combination across all generated NFTs; and (c) optional inclusion/exclusion rules between traits. Return the generated items and report when generation is impossible. Describe your data structures, algorithm, complexity, and test strategy.