Katkat
Back

Generate Every Ordered Sum Using Ones and Twos

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests backtracking and recursion to generate all valid ordered compositions of a target integer using only digits 1 and 2 in lexicographical order.

Problem Statement

Given an integer n, generate all ordered strings consisting exclusively of the characters '1' and '2' such that the sum of their numeric values equals n.

The results must be returned in lexicographical (alphabetical) order with no duplicates.

Function Signature

def generate_ordered_sums(n: int) -> list[str]:
    pass

Input & Output Format

  • Input: A single integer n (0 <= n <= 25).
  • Output: A list of strings, where each string contains only '1' and '2', its digits sum to n, and the list is sorted in ascending lexicographical order.

Examples

Example 1

Input: n = 3
Output: ["111", "12", "21"]

Explanation:

  • '1' + '1' + '1' = 3
  • '1' + '2' = 3
  • '2' + '1' = 3

Sorted lexicographically, "111" < "12" < "21".

Example 2

Input: n = 4
Output: ["1111", "112", "121", "211", "22"]

Explanation: All permutations of 1s and 2s that sum to 4, ordered lexicographically.

Constraints

  • 0 <= n <= 25
  • Note: When n = 0, the only valid string is the empty string "", yielding [""].

Edge Cases to Consider

  • n = 0: Should return [""] (the empty sum).
  • n = 1: Should return ["1"].
  • n = 2: Should return ["11", "2"].

Hints

Hint 1

Notice that the number of sequences that sum to n follows the Fibonacci sequence, as each sequence must end (or begin) with either a 1 or a 2.

Hint 2

To guarantee lexicographical order naturally, always branch on '1' before branching on '2' during your recursion.

Hint 3

Pass down the remaining sum required; when the remaining sum hits 0, record the current sequence, and prune the branch immediately if the sum becomes negative.

Follow-up questions

  • What is the time and space complexity of your solution, and how does the total count of sequences relate to the Fibonacci numbers?
  • How would you redesign the interface if `n` were up to 40 and the caller only wanted an iterator/generator to stream sequences one at a time without storing all in memory?
  • How would you find just the k-th lexicographical sequence directly without generating all preceding sequences?