題：
給定一個只包含數(shù)字的字符串虚茶，復(fù)原它并返回所有可能的 IP 地址格式仇参。
示例:
輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/restore-ip-addresses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)冈敛，非商業(yè)轉(zhuǎn)載請注明出處。
解：
此題又是一道典型的「回溯」類題目暮蹂。
「回溯」的「循環(huán)不變式」不夠明顯：通過遞歸枚舉所有可能寞缝⊙鲂海回退時，恢復(fù)現(xiàn)場被啼；終止時棠枉，更新答案集浓体。
對于這道具體的題目辈讶，要通過耐心分析找到一個恰當(dāng)?shù)倪f歸枚舉方式，然后就是篩選出每一次遞歸枚舉時的所有有效選擇生闲。
此題好玩的地方在于這個判斷有效選擇的條件比較繁瑣月幌，此時適合抽出布爾變量碍讯。
var restoreIpAddresses = function(s) {
const ans = []
const choices = []
const l = s.length
// 輔助函數(shù)
function parseIP() {
const IP = choices.join('')
if (IP.split('.').every(e => parseInt(e) < 256)) ans.push(IP)
}
function backtrack(i = 0, pointCount = 0, last = -1, sliceLength = 0) {
// 遞歸終止扯躺，嘗試添加有效 IP
if (pointCount === 3 && i === l) parseIP()
// 越界直接返回，或許可以不需要轴术，但放在這里更安全
else if (pointCount > 3 || i > l) return
// 回溯：遞歸 + 回退前清理現(xiàn)場
else {
// 一共兩種可能
const canPushNumber = (sliceLength > 0 && sliceLength < 3 && choices[last + 1 - sliceLength] != '0') || sliceLength === 0
const canPushPoint = sliceLength > 0 && sliceLength <= 3
// 分別對兩種可能進(jìn)行操作
if (canPushNumber) {
choices[last + 1] = s[i]
backtrack(i + 1, pointCount, last + 1, sliceLength + 1)
}
if (canPushPoint) {
choices[last + 1] = '.'
backtrack(i, pointCount + 1, last + 1, 0)
}
// 回退之前清理現(xiàn)場
choices.length = last + 1
}
}
backtrack()
return ans
};
