Restore Dotted Addresses from an Unchanged Digit Sequence

### Problem Insert three dots into the digit string `s` to form all possible valid IPv4 addresses. Each address has exactly four decimal components, each from 0 through 255. A component cannot have a leading zero unless it is the single digit `0`. Keep every digit in its original order; do not delete or reorder digits. Return all valid addresses in any order, or an empty collection if none can be formed. ```cpp vector<string> restoreIpAddresses(string s); ``` ### Examples ```text Input: s = "1111" Output: ["1.1.1.1"] ``` ```text Input: s = "010010" One valid output: ["0.100.1.0","0.10.0.10"] ``` ### Constraints & Assumptions - `1 <= s.length <= 20`. - Every character is a decimal digit. - Only dots may be inserted. A valid address has four nonempty components and no multi-digit component starting with zero. ### Clarifying Questions to Ask - Is `00` a valid spelling of zero? No; only `0` is valid. - Must an address consume all digits? Yes. - Must the returned addresses be sorted? No. ```hint Check both kinds of validity A numerically small component can still be invalid because of its spelling. Every digit must belong to one of exactly four components. ``` ### What a Strong Answer Covers - Four-component partitioning with no lost or reordered digit. - Inclusive 0..255 bounds and leading-zero handling. - Complete enumeration without duplicate addresses and a bounded search cost. ### Follow-up Questions - Which input lengths can immediately be ruled out? - How can equivalent address collections be compared without imposing an order?