题目1 --组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
go语言题解
func combinationSum(candidates []int, target int) [][]int {
result := make([]int, 0)
results := make([][]int, 0)
sort.Ints(candidates)
return dfs(candidates, target, result, results, 0)
}
func dfs(candidates []int, target int, result []int, results [][]int, begin int) [][]int{
if target == 0 {
tmp := make([]int, len(result))
copy(tmp, result)
results = append(results, tmp)
return results
}else{
for i:=begin; i< len(candidates); i++{
newtarget := target - candidates[i]
//剪枝
if newtarget < 0{
break
}
if newtarget >= 0{
result = append(result, candidates[i])
results = dfs(candidates, newtarget, result, results, i)
result = result[0:len(result)-1] //注意回溯，以及如何去重
}
}
}
return results
}
题目2 组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
go题解
func combinationSum2(candidates []int, target int) [][]int {
result := make([]int, 0)
results := make([][]int, 0)
sort.Ints(candidates)
return dfs(candidates, target, result, results, 0)
}
func dfs(candidates []int, target int, result []int, results [][]int, begin int) [][]int{
fmt.Println(candidates)
if target == 0 {
tmp := make([]int, len(result))
copy(tmp, result)
results = append(results, tmp)
return results
}else{
//可以不用截取candidates，而是通过begin和i+1传入candidates的索引来做去重
for i:=begin; i< len(candidates); i++{
newtarget := target - candidates[i]
//剪枝
if newtarget < 0{
break
}
//有相同数字的话，也会有重复组合。所以在排序之后，重复的数字可以考虑值做一次排列
if i > begin && candidates[i] == candidates[i-1]{
continue
}
if newtarget >= 0{
result = append(result, candidates[i])
results = dfs(candidates, newtarget, result, results, i+1)
result = result[0:len(result)-1] //注意回溯，以及如何去重
}
}
}
return results
}
题目3 电话号码组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
go语言题解
func letterCombinations(digits string) []string {
letters := []string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
return dfs(digits, letters)
}
func dfs(digits string, letters []string) []string{
lenofdigits := len(digits)
if lenofdigits == 1{
index,_ := strconv.ParseInt(digits, 10, 32)
letter := letters[index]
return stringTolist(letter)
}else{
index,_ := strconv.ParseInt(digits[0:1], 10, 32)
letter := letters[index]
newfront := stringTolist(letter)
newdigist := digits[1 : lenofdigits]
newtail := dfs(newdigist, letters)
// fmt.Println(newdigist, type(newdigist))
return stringArrAdd(newfront, newtail)
}
}
func stringTolist(str string) []string{
letterStrings := make([]string, 0)
for _,v :=range str{
letterStrings = append(letterStrings, string(v))
}
return letterStrings
}
func stringArrAdd(a []string, b []string) []string{
finalstr := make([]string, 0)
for _,va := range a{
for _,vb := range b{
newstr := va+vb
finalstr = append(finalstr, newstr)
}
}
return finalstr
}
