Generate Every Ordered Sum Using Ones and Twos
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Generate Every Ordered Sum Using Ones and Twos
Given a positive integer `n`, return every string made only of the characters `"1"` and `"2"` whose digit values sum to `n`.
The order of characters matters: `"12"` and `"21"` are different results. Return the strings in ascending lexicographic order, with `"1"` ordered before `"2"`.
## Function Signature
```python
def ordered_sums(n: int) -> list[str]:
...
```
## Constraints
- `1 <= n <= 25`
- Every returned string must have digit sum exactly `n`.
- Return each valid string exactly once.
## Examples
```text
Input: n = 3
Output: ["111", "12", "21"]
```
```text
Input: n = 4
Output: ["1111", "112", "121", "211", "22"]
```
Quick Answer: Generate every ordered string of ones and twos whose digit values sum to a target integer, with no duplicates and lexicographic output. The problem tests complete enumeration, deterministic ordering, small-target edge cases, and reasoning about an inherently exponential result set.