39. 组合总和

• 暴力

var res [][]int
var temp []int
var mp = make(map[string]bool)

func addMap(arr []int) {
    sort.Ints(arr)
    key := ""
    for _, val := range arr {
        key += strconv.Itoa(val) + ","
    }
    mp[key] = true
}
func exists(arr []int) bool {
    sort.Ints(arr)
    key := ""
    for _, val := range arr {
        key += strconv.Itoa(val) + ","
    }
    return mp[key] == true
}
func dfs(candidates []int, target int) {
    if target == 0 {
        arr := make([]int, len(temp))
        copy(arr, temp)
        if !exists(arr) {
            res = append(res, arr)
            addMap(arr)
        }
        return
    }
    for i := 0; i < len(candidates); i++ {
        if candidates[i] > target {
            return
        }
        temp = append(temp, candidates[i])
        dfs(candidates, target-candidates[i])
        temp = temp[:len(temp)-1]
    }
}
func combinationSum(candidates []int, target int) [][]int {
    res = [][]int{}
    temp = []int{}
    mp = make(map[string]bool)
    sort.Ints(candidates)
    dfs(candidates, target)
    return res
}

• 加入startIndex优化mp

var res [][]int
var temp []int

func dfs(candidates []int, target, startIndex int) {
    if target == 0 {
        arr := make([]int, len(temp))
        copy(arr, temp)

        res = append(res, arr)
        return
    }
    for i := startIndex; i < len(candidates); i++ {
        if candidates[i] > target {
            return
        }
        temp = append(temp, candidates[i])
        dfs(candidates, target-candidates[i], i)
        temp = temp[:len(temp)-1]
    }
}
func combinationSum(candidates []int, target int) [][]int {
    res = [][]int{}
    temp = []int{}
    sort.Ints(candidates)
    dfs(candidates, target, 0)
    return res
}

40.组合总和II

var res = [][]int{}
var temp = []int{}
var mp = make(map[string]bool)

func dfs(candidates []int, target, startIndex int) {
    if target == 0 {
        key := ""
        for i := 0; i < len(temp); i++ {
            key += strconv.Itoa(temp[i]) + ","
        }
        if !mp[key] {
            arr := make([]int, len(temp))
            copy(arr, temp)
            res = append(res, arr)
            mp[key] = true
        }
        return
    }
    for i := startIndex; i < len(candidates); i++ {
        if candidates[i] > target {
            break
        }
        temp = append(temp, candidates[i])
        dfs(candidates, target-candidates[i], i+1)
        temp = temp[:len(temp)-1]
    }
}
func combinationSum2(candidates []int, target int) [][]int {
    res = [][]int{}
    temp = []int{}
    mp = make(map[string]bool)
    sort.Ints(candidates)
    dfs(candidates, target, 0)
    return res
}

---

• 分类： 未分类
• 标签： 无标签