• 组合总和

1.数组中每个元素在每个组合中可以使用无数次（递归中传入 i）

2.数组中无重复元素（排序+剪枝）

3.输出结果不能包含重复组合（for 循环 i 从 start 开始遍历）

代码如下：

var (
    path []int
    result [][]int
)

func combinationSum(candidates []int, target int) [][]int {
    path = []int{}
    result = [][]int{}
    sort.Ints(candidates)
    dfs(candidates, target, 0)
    return result
}

func dfs(candidates []int, target int, start int) {
    if target == 0 {
        temp := make([]int, len(path))
        copy(temp, path)
        result = append(result, temp)
        return 
    }

    for i := start; i < len(candidates); i++ {
        if candidates[i] > target {
            break
        }
        path = append(path, candidates[i])
        dfs(candidates, target - candidates[i], i)
        path = path[:len(path)-1]
    }
}

• 组合总和II

1.数组中每个数字在每个组合中只能用一次（递归中传入 i+1）

2.数组中有重复元素（排序+剪枝+树层去重）

3.输出结果不能包含重复组合（for 循环 i 从 start 开始遍历）

解决方法：

1.每个元素只能使用一次，递归 dfs 时传入 i+1，表示当前数字只能用一次

2.对数组排序，做剪枝操作

3.引入 bool 类型的 used 数组，对同一层节点进行去重:

4.发现同层节点重复后，做continue操作

// 排序
sort.Ints(nums)

// 剪枝
if nums[i] > target {
    break
}

// 树层去重
if i > 0 && nums[i] == nums[i-1] && used[i-1] == false {
    continue
}

代码如下：

var (
    path []int
    result [][]int
    used []bool
)

func combinationSum2(candidates []int, target int) [][]int {
    path = []int{}
    result = [][]int{}
    used = make([]bool, len(candidates))
    sort.Ints(candidates)
    dfs(candidates, target, 0)
    return result
}

func dfs(candidates []int, target int, start int) {
    if target == 0 {
        temp := make([]int, len(path))
        copy(temp, path)
        result = append(result, temp)
        return
    }
    
    for i := start; i < len(candidates); i++ {
        if candidates[i] > target {
            break
        }
        if i > 0 && candidates[i-1] == candidates[i] && used[i-1] == false {
            continue
        }
        path = append(path, candidates[i])
        used[i] = true
        dfs(candidates, target - candidates[i], i+1)
        path = path[:len(path)-1]
        used[i] = false
    }
}

• 组合总和III

1.数组中每个数字在每个组合中只能用一次（递归中传入 i+1）

2.数组中无重复数字（排序+剪枝）

3.输出结果不能包含重复数组（for 循环 i 从 start 开始遍历）

代码如下：

var (
    path []int
    result [][]int
)

func combinationSum3(k int, n int) [][]int {
    path = []int{}
    result = [][]int{}
    dfs(k, n, 1)
    return result
}

func dfs(k int, n int, start int) {
    if n == 0 {
        if len(path) == k {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
        }
        return
    }

    for i := start; i < 10; i++ {
        if i > n {
            break
        }
        path = append(path, i)
        dfs(k, n - i, i + 1)
        path = path[:len(path)-1]
    }
}

• 组合总和IV

1.数组中每个数字在每个组合中可以使用无数次（递归中传入 i）

2.数组中无重复元素（排序+剪枝）

3.输出结果中包含重复数组（for 循环中 i 从 0开始遍历）

组合总和IV按照递归解法虽然测试样例通过，但是最终超时，说明对于最终结果包含重复数组来说，不能只通过递归的剪枝来优化，需要用到别的方法，后续补充 dp 解法。

代码如下：

var (
    count int
)

func combinationSum4(nums []int, target int) int {
    count = 0
    sort.Ints(nums)
    dfs(nums, target, 0)
    return count
}

func dfs(nums []int, target int, start int) {
    if target == 0 {
        count++
        return
    }

    for i := 0; i < len(nums); i++ {
        if nums[i] > target {
            break
        }
        dfs(nums, target - nums[i], i)
    }
}

对于从多个字符串集合中进行组合的情况，如 17. 电话号码的字母组合 这道题中，每个数字所对应的值都是一个字符串，for 循环的 i 就要从 0 开始，dfs 传入的参数 start 代表下一个数字（即下一个字符串）。

从代码层面进行解析：

var (
    path []byte                // 保存数字对应的字母组合,go 里面的字符类型采用 byte
    result []string            
    digitMap map[int]string    // 保存数字与字母组合的映射
)

func letterCombinations(digits string) []string {
    path = []byte{}
    result = []string{}
    if digits == "" {
        return result
    }
    digitMap = map[int]string{
        2 : "abc",
        3 : "def",
        4 : "ghi",
        5 : "jkl",
        6 : "mno",
        7 : "pqrs",
        8 : "tuv",
        9 : "wxyz",
    }
    dfs(digits, 0)
    return result
}

func dfs(digits string, start int) {
    if len(path) == len(digits) {
        result = append(result, string(path))  // 将字符数组转成字符串
        return
    }

    str := digitMap[int(digits[start] - '0')]  // 取数值类型字符串的单个数值字符
    for i := 0; i < len(str); i++ {    // 这道题是不同的字符串集合,所以 i 从 0 开始
        path = append(path, str[i])
        dfs(digits, start+1)     // start 代表 digits 的索引,递归传入的是 digits 的下一个数字
        path = path[:len(path)-1]
    }
}

小细节：Go 中对字符串类型取某一个字符时得到的是ASCII码，需要手动将其转成对应的数据类型

比如字符串 num := “123”, 获取第一位的字符 1，可以用 byte(num[1])、int(num[1] – ‘0’)、string(num[1])。不管想要转成什么数据结构，都要手动转成对应的数据结构，特别对于 int 类型转换，需要将 ASCII 码减去 ‘0’ 来得到对应的数字符号，’0′ 的 ASCII 码是 48 ，’1′ 的 ASCII 码是 49。