93.复原IP地址

• 回溯，细节多

var res []string
var offsets []int

func valid(s string) bool {
    if len(s) > 1 && s[0] == '0' {
        return false
    }
    parseInt, _ := strconv.ParseInt(s, 10, 64)
    return parseInt <= 255
}
func dfs(str string, startIndex int) {
    if len(offsets) == 4 {
        ip_1 := str[offsets[0]:offsets[1]]
        ip_2 := str[offsets[1]:offsets[2]]
        ip_3 := str[offsets[2]:offsets[3]]
        ip_4 := str[offsets[3]:]
        if !valid(ip_1) || !valid(ip_2) || !valid(ip_3) || !valid(ip_4) {
            return
        }
        ip := strings.Join([]string{ip_1, ip_2, ip_3, ip_4}, ".")
        res = append(res, ip)
        return
    }
    for i := startIndex; i < startIndex+3 && i < len(str); i++ {
        offsets = append(offsets, i)
        ipPart := str[offsets[len(offsets)-2]:offsets[len(offsets)-1]]
        if ipPart == "" {
            offsets = offsets[:len(offsets)-1]
            continue
        }
        if !valid(ipPart) {
            offsets = offsets[:len(offsets)-1]
            break
        }
        dfs(str, i+1)
        offsets = offsets[:len(offsets)-1]
    }

}
func restoreIpAddresses(s string) []string {
    res = []string{}
    offsets = []int{}
    offsets = append(offsets, 0)
    dfs(s, 1)
    return res
}

78.子集

var res [][]int
var temp []int
func dfs (nums []int, startIndex int) {
    if startIndex >= len(nums) {
        // cp := make([]int, len(temp))
        // copy(cp, temp)
        // res = append(res, cp)
        return
    }
    for i := startIndex; i < len(nums); i++ {
        temp = append(temp, nums[i])
        cp := make([]int, len(temp))
        copy(cp, temp)
        res = append(res, cp)
        dfs(nums, i+1)
        temp = temp[:len(temp)-1]
    }
}
func subsets(nums []int) [][]int {
    res = [][]int{}
    temp = []int{}
    res = append(res, []int{})
    dfs(nums, 0)
    return res
}

90.子集II

var res [][]int
var temp []int
func dfs (nums []int, startIndex int) {
    if startIndex >= len(nums) {
        return 
    }
    for i := startIndex; i < len(nums); i++ {
        temp = append(temp, nums[i])
        cp := make([]int, len(temp))
        copy(cp, temp)
        sort.Ints(cp)
        res = append(res, cp)
        dfs(nums, i+1)
        val := temp[len(temp)-1]
        for i < len(nums) && nums[i] == val {
            i++
        }
        i--
        temp = temp[:len(temp)-1]
    }
}
func subsetsWithDup(nums []int) [][]int {
    res = [][]int{}
    temp = []int{}
    sort.Ints(nums)
    res = append(res, []int{})
    dfs(nums, 0)
    return res
}

---

• 分类： 算法
• 标签： 算法基础 回溯