Restore IP Addresses and Word Break II: Partition Backtracking

def restoreIpAddresses(s):
    result = []
    def bt(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append('.'.join(parts))
            return
        for length in range(1, 4):
            if start + length > len(s): break
            seg = s[start:start+length]
            # No leading zeros; no value > 255
            if (len(seg) > 1 and seg[0] == '0') or int(seg) > 255:
                break
            parts.append(seg)
            bt(start + length, parts)
            parts.pop()
    bt(0, [])
    return result

print(restoreIpAddresses("25525511135"))
# ['255.255.11.135', '255.255.111.35']

# Word Break II: find all segmentations
def wordBreak(s, wordDict):
    word_set = set(wordDict)
    memo = {}
    def bt(start):
        if start in memo: return memo[start]
        if start == len(s): return [[]]
        result = []
        for end in range(start+1, len(s)+1):
            word = s[start:end]
            if word in word_set:
                for rest in bt(end):
                    result.append([word] + rest)
        memo[start] = result
        return result
    return [' '.join(sentence) for sentence in bt(0)]

print(wordBreak("catsanddog", ["cat","cats","and","sand","dog"]))
# ['cat sand dog', 'cats and dog']

#include <bits/stdc++.h>
using namespace std;

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    vector<string> parts;
    function<void(int)> bt = [&](int start) {
        if (parts.size() == 4) {
            if (start == (int)s.size()) result.push_back(parts[0]+"."+parts[1]+"."+parts[2]+"."+parts[3]);
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > (int)s.size()) break;
            string seg = s.substr(start, len);
            if ((seg.size() > 1 && seg[0]=='0') || stoi(seg) > 255) break;
            parts.push_back(seg);
            bt(start + len);
            parts.pop_back();
        }
    };
    bt(0);
    return result;
}