Worked Hours String (Backtracking)

Problem Statement

Generate all strings of length 7 where each character is either a digit '0'-'9' or the character '#' (representing 0), such that the sum of the digit values in the string equals a given target N. The # contributes 0 to the sum.

Return the list of valid strings (or the count, depending on the exact variant).

Example 1:

Input: N = 1
Output: [
  "#######",  // impossible — sum 0, not 1. Removed.
  "1######", "#1#####", "##1####", "###1###", "####1##", "#####1#", "######1",
  "0000001", "0000010", "0000100", ...  // depending on how digits-with-leading-zero are handled
]

Exact output depends on whether "digits 0-9 at a position" and "# at a position" produce distinct strings (they do, since the character itself differs).

Example 2:

Input: N = 63
Output: ["9999999"] (only one way: all nines, sum = 63).

Constraints:

0 <= N <= 63 (max sum of seven 9s).
Length is fixed at 7.

Difficulty: Medium Round: OA

Pattern Recognition

What is the input structure? A target integer.
What are we optimizing? Enumerate all length-7 strings over an 11-symbol alphabet (0-9 + #) whose digit-sum equals N.
What pattern does this fit? Backtracking with pruning.
Why does this pattern fit? You build the string position by position, trying each symbol. Pruning rule: if the partial sum already exceeds N, abort this branch.

Without pruning, the search space is 11^7 ≈ 19.5 million. With the "partial sum > N" prune, most branches are cut early.

Approach

Brute Force — Enumerate All 11^7 Strings

Generate every length-7 string over {0-9, #} and check the sum.

Time: O(11^7) ≈ 2 * 10^7. Space: O(7) for the current string. Why marginal: Already tractable but wasteful. Pruning cuts this dramatically.

Optimal — Backtracking with Sum Prune

Key Insight: At each position, track the running sum. If adding digit d makes sum + d > N, stop — no larger digit will work either (since we try digits in order), and deeper positions cannot decrease the sum.

Step-by-step:

Maintain a buffer buf[0..6] and current position pos and running sum.
Base case: pos == 7. If sum == N, emit buf as a string.
Recurse:
- Place '#' at buf[pos], recurse with same sum.
- For d from 0 to 9:
  - If sum + d > N, break (loop is monotone).
  - Place d at buf[pos], recurse with sum + d.

Time: O(valid answers * 7) for emission, O(pruned states * 7) for exploration. Typical size: a few thousand. Space: O(7) recursion depth.

Walkthrough (Partial)

For N = 1, position 0:

Place '#' → sum = 0. Recurse into position 1 with sum 0.
Place '0' → sum = 0. Recurse with sum 0.
Place '1' → sum = 1. Recurse with sum 1.
Place '2' → sum = 2. But 2 > 1 → break.

At position 1 (sum = 1 arriving from placing '1' at position 0):

Place '#' → sum stays 1. Recurse.
Place '0' → sum stays 1. Recurse.
Place '1' → sum = 2. But 2 > 1 → break.

Continuing this way, you enumerate all placements of a single 1 or 0s and #s elsewhere, emitting strings when position = 7 and sum = 1.

Each emitted string is length 7, with exactly one '1' and six characters each being '0' or '#' — so 7 placements * 2^6 = 448 such strings for N = 1.

Implementation

TypeScriptC++

typescript

function workedHoursStrings(targetSum: number): string[] {
    const result: string[] = [];
    const buf: string[] = new Array(7);

    const backtrack = (pos: number, sum: number) => {
        if (pos === 7) {
            if (sum === targetSum) result.push(buf.join(""));
            return;
        }

        // Option 1: place '#' (contributes 0).
        buf[pos] = "#";
        backtrack(pos + 1, sum);

        // Option 2: place digit 0-9, with pruning.
        for (let d = 0; d <= 9; d++) {
            if (sum + d > targetSum) break; // monotone prune
            buf[pos] = String(d);
            backtrack(pos + 1, sum + d);
        }
    };

    backtrack(0, 0);
    return result;
}

cpp

#include <string>
#include <vector>

void backtrack(int pos, int sum, int target, std::string& buf, std::vector<std::string>& out) {
    if (pos == 7) {
        if (sum == target) out.push_back(buf);
        return;
    }

    // Place '#'.
    buf[pos] = '#';
    backtrack(pos + 1, sum, target, buf, out);

    // Place digits 0-9 with pruning.
    for (int d = 0; d <= 9; d++) {
        if (sum + d > target) break;
        buf[pos] = '0' + d;
        backtrack(pos + 1, sum + d, target, buf, out);
    }
}

std::vector<std::string> workedHoursStrings(int targetSum) {
    std::vector<std::string> out;
    std::string buf(7, '#');
    backtrack(0, 0, targetSum, buf, out);
    return out;
}

Watch out:

Treating '#' and '0' as equivalent. They both contribute 0 to the sum but are different characters, so "####000" and "0000000" are both valid and distinct.
Not pruning. 11^7 ≈ 20 million raw states. Emitting a million results can TLE.
Off-by-one on target. The constraint sum + d > target cuts correctly; >= would miss valid placements.

Complexity Analysis

	Time	Space
Brute Force	O(11^7)	O(7)
Optimal (Backtracking + Prune)	Output-sensitive, O(answers * 7)	O(7)

Bottleneck: The number of valid strings. For N = 31 (middle of the range), the answer set is largest — around 10,000-50,000 strings.

Edge Cases

N = 0 — only strings with no nonzero digits. Each position is '0' or '#' → 2^7 = 128 strings.
N = 63 — only "9999999". 1 string.
N > 63 — impossible. Return empty list.
N < 0 — invalid input. Return empty list or throw.
Large result set (N = 30-35) — memory can grow; ensure your result list is sized reasonably.

LC 77 — Combinations — Classic backtracking template with prune.
LC 216 — Combination Sum III — Pick k distinct digits summing to n; same flavor.
LC 39 — Combination Sum — Backtracking with unbounded use of each number.
LC 22 — Generate Parentheses — Backtracking with prune by invariant.

OA Strategy Notes

Medium OA problem, 20-30 minutes. The risk is not pruning (TLE). Write the base case first, then the two symbol branches, then the prune. Trace on N=1 to verify output format before submitting.

What is Expected at Each Level

Junior: Brute force, 11^7 enumeration. May TLE. With a hint about pruning, adds the sum-check.

Mid-level: Goes to backtracking with sum-prune directly. Handles N=0 and N>63 edge cases.

Senior: Discusses the combinatorial count (multinomial coefficients), mentions that counting could be done without enumeration via DP on (position, sum), and offers a DP solution for the "how many" variant in O(7 * 64).

Worked Hours String (Backtracking) ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Enumerate All 11^7 Strings ​

Optimal — Backtracking with Sum Prune ​

Walkthrough (Partial) ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

OA Strategy Notes ​

What is Expected at Each Level ​