All Distinct-Integer Sets With Given Sum and Product

Reported in interviews at Jump Trading

Problem statement

Given positive integers $S$ and $P$, find every set of distinct positive integers whose elements sum to $S$ and multiply to $P$.

Constraints

  • $0 < S, P < 10^8$.

Examples

  • $S = 6$, $P = 6$ -> $\{1, 2, 3\}$ and $\{6\}$ (both sum to 6 and multiply to 6).
Show hint

Which search technique enumerates sets under two running constraints, and what ordering keeps each set from appearing more than once?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems