# leetcode 回溯题目 golang语言

`````` 链接：https://leetcode-cn.com/tag/backtracking/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。``````

## 78.子集，不含重复元素

``````func subsets(nums []int) [][]int {
result := make([][]int, 0)
subsetsBT(&result, nums, []int{}, 0)
return result
}
func subsetsBT(result *[][]int, nums []int, temp []int, start int) {
//此处深拷贝temp，避免回溯的时候temp被修改后会影响之前保存的结果
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)

for i := start; i < len(nums); i++ {
temp = append(temp, nums[i])
subsetsBT(result, nums, temp, i+1)//不包含重复值
temp = temp[:len(temp)-1]
}
}``````

``````func subsets(nums []int) [][]int {
result := make([][]int, 0)
n := 1 << uint(len(nums))
for i := 0; i < n; i++ {
temp := make([]int, 0)
for j := 0; j < len(nums); j++ {
if uint(i)>>uint(j)&1 == 1 {
temp = append(temp, nums[j])
}
}
result = append(result, temp)
}

return result
}``````

## 77.组合

``````func combine(n int, k int) [][]int {
var result = make([][]int, 0)
combineBT(n, k, 1, []int{}, &result)
return result
}
func combineBT(n, k, start int, temp []int, result *[][]int) {
if len(temp) == k {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}

for i := start; i <= n; i++ {
temp = append(temp, i)
combineBT(n, k, i+1, temp, result)
temp = temp[0 : len(temp)-1]
}
}``````

## 39. 组合总和，不包含重复元素，可多次使用

``````
func combinationSum(candidates []int, target int) [][]int {
var result = make([][]int, 0)
sort.Ints(candidates)
combinationSumBT(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT(result, candidates, temp, target, i)//可以包含已经用过的值，所以从i开始，
temp = temp[0 : len(temp)-1]//回溯
target += candidates[i]//得把当前用过的值再加回去。
} else {
return
}
}
}``````

## 40. 组合总和2，只能使用一次且解空间不能包含重复

``````func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
var result = make([][]int, 0)
combinationSumBT2(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT2(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
//比如[10,1,2,7,6,1,5], target = 8
//排好序后[1,1,2,5,6,7,10]
//在第一个for循环里，先遍历到第一个1，经过一系列操作，得到解集[1,7]
//然后还是第一个for循环里，又遍历到后面的1，现在是不需要[第二个1,7]这个解集了，所以跳过。
if i != start && candidates[i] == candidates[i-1] { //因为解空间不能有重复
continue
}
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT2(result, candidates, temp, target, i+1)//因为不能重复使用，所以从i+1开始
temp = temp[0 : len(temp)-1]
target += candidates[i]
} else {
return
}
}
}
``````

## 216. 组合总和3,只有1-9，且每个组合中不能有重复且最后的解空间不能包含重复

``````func combinationSum3(k int, n int) [][]int {
var result = make([][]int, 0)
combinationSumBT3(&result, []int{}, k, n, 1)
return result
}
func combinationSumBT3(result *[][]int, temp []int, k int, target int, start int) {
//和第一个很像，在target的基础上增加了一个k的限制。
if target == 0 && k == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i <= 9; i++ {
if target-i >= 0 {
target -= i
k--
temp = append(temp, i)
combinationSumBT3(result, temp, k, target, i+1)//每个组合不能有重复
temp = temp[0 : len(temp)-1]
target += i
k++
} else {
return
}
}
}
``````

## 17.电话号码的字母组合

``````var wordsMap = map[int]string{2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
}
func letterCombinationsBT(answer *[]string, digits string, temp string, index int) {
if len(temp) == len(digits) {
return
}

char := digits[index] - '0'
letter := wordsMap[int(char)]
//fmt.Println(int(char), letter)
for i := 0; i < len(letter); i++ {
}

return
}``````

" "

a b c

c ad ae af bd be bf

ad ae af bd be bf cd ce cf

``````
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
var words = [8]string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
queue := make([]string, 0)
queue = append(queue, "")
for i := 0; i < len(digits); i++ {
n := digits[i] - '2'
size := len(queue)
for j := 0; j < size; j++ {
st := queue[0]
queue = queue[1:]
for _, ch := range words[n] {
temp := st + string(ch)
queue = append(queue, temp)
}
}
}
return queue
}``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

`````` 链接：https://leetcode-cn.com/tag/backtracking/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。``````

## 78.子集，不含重复元素

``````func subsets(nums []int) [][]int {
result := make([][]int, 0)
subsetsBT(&result, nums, []int{}, 0)
return result
}
func subsetsBT(result *[][]int, nums []int, temp []int, start int) {
//此处深拷贝temp，避免回溯的时候temp被修改后会影响之前保存的结果
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)

for i := start; i < len(nums); i++ {
temp = append(temp, nums[i])
subsetsBT(result, nums, temp, i+1)//不包含重复值
temp = temp[:len(temp)-1]
}
}``````

``````func subsets(nums []int) [][]int {
result := make([][]int, 0)
n := 1 << uint(len(nums))
for i := 0; i < n; i++ {
temp := make([]int, 0)
for j := 0; j < len(nums); j++ {
if uint(i)>>uint(j)&1 == 1 {
temp = append(temp, nums[j])
}
}
result = append(result, temp)
}

return result
}``````

## 77.组合

``````func combine(n int, k int) [][]int {
var result = make([][]int, 0)
combineBT(n, k, 1, []int{}, &result)
return result
}
func combineBT(n, k, start int, temp []int, result *[][]int) {
if len(temp) == k {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}

for i := start; i <= n; i++ {
temp = append(temp, i)
combineBT(n, k, i+1, temp, result)
temp = temp[0 : len(temp)-1]
}
}``````

## 39. 组合总和，不包含重复元素，可多次使用

``````
func combinationSum(candidates []int, target int) [][]int {
var result = make([][]int, 0)
sort.Ints(candidates)
combinationSumBT(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT(result, candidates, temp, target, i)//可以包含已经用过的值，所以从i开始，
temp = temp[0 : len(temp)-1]//回溯
target += candidates[i]//得把当前用过的值再加回去。
} else {
return
}
}
}``````

## 40. 组合总和2，只能使用一次且解空间不能包含重复

``````func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
var result = make([][]int, 0)
combinationSumBT2(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT2(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
//比如[10,1,2,7,6,1,5], target = 8
//排好序后[1,1,2,5,6,7,10]
//在第一个for循环里，先遍历到第一个1，经过一系列操作，得到解集[1,7]
//然后还是第一个for循环里，又遍历到后面的1，现在是不需要[第二个1,7]这个解集了，所以跳过。
if i != start && candidates[i] == candidates[i-1] { //因为解空间不能有重复
continue
}
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT2(result, candidates, temp, target, i+1)//因为不能重复使用，所以从i+1开始
temp = temp[0 : len(temp)-1]
target += candidates[i]
} else {
return
}
}
}
``````

## 216. 组合总和3,只有1-9，且每个组合中不能有重复且最后的解空间不能包含重复

``````func combinationSum3(k int, n int) [][]int {
var result = make([][]int, 0)
combinationSumBT3(&result, []int{}, k, n, 1)
return result
}
func combinationSumBT3(result *[][]int, temp []int, k int, target int, start int) {
//和第一个很像，在target的基础上增加了一个k的限制。
if target == 0 && k == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i <= 9; i++ {
if target-i >= 0 {
target -= i
k--
temp = append(temp, i)
combinationSumBT3(result, temp, k, target, i+1)//每个组合不能有重复
temp = temp[0 : len(temp)-1]
target += i
k++
} else {
return
}
}
}
``````

## 17.电话号码的字母组合

``````var wordsMap = map[int]string{2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
}
func letterCombinationsBT(answer *[]string, digits string, temp string, index int) {
if len(temp) == len(digits) {
return
}

char := digits[index] - '0'
letter := wordsMap[int(char)]
//fmt.Println(int(char), letter)
for i := 0; i < len(letter); i++ {
}

return
}``````

" "

a b c

c ad ae af bd be bf

ad ae af bd be bf cd ce cf

``````
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
var words = [8]string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
queue := make([]string, 0)
queue = append(queue, "")
for i := 0; i < len(digits); i++ {
n := digits[i] - '2'
size := len(queue)
for j := 0; j < size; j++ {
st := queue[0]
queue = queue[1:]
for _, ch := range words[n] {
temp := st + string(ch)
queue = append(queue, temp)
}
}
}
return queue
}``````