LeetCode-题目整理【11】：回溯算法

下面这些题目的解答，都使用到回溯算法解答，通过找到目标条件，满足之后就可以返回；另外可以使用 剪枝，减少调用递归的次数，减少时间。

17. 电话号码的字母组合
    中等
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    示例 1：
    输入：digits = “23”
    输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
    示例 2：
    输入：digits = “”
    输出：[]
    示例 3：
    输入：digits = “2”
    输出：[“a”,“b”,“c”]

func letterCombinations(digits string) []string {
   
	if len(digits) == 0 {
   
		return []string{
   }
	}

	digitMap := map[byte]string{
   
		'2': "abc",
		'3': "def",
		'4': "ghi",
		'5': "jkl",
		'6': "mno",
		'7': "pqrs",
		'8': "tuv",
		'9': "wxyz",
	}

	var result []string
	var backtrack func(current string, index int)
	backtrack = func(current string, index int) {
   
		//因为“23”那么其字母组合也只能是两位，如果是“234”则组合是3位
		if index == len(digits) {
   
			result = append(result, current)
			return
		}

		letters := digitMap[digits[index]]
		for i := 0; i < len(letters); i++ {
   
			//字符串是由字节组成的，因此在遍历字符串时，每个元素是一个字节（byte）----》string(letters[i])
			backtrack(current + string(letters[i]), index+1)
		}
	}

	backtrack("", 0)
	return result
}

Go 语言中的字符串实际上是一个不可变的字节切片，用于存储文本数据。每个字节表示字符串中的一个字符，其中每个字符可能占用一个或多个字节，具体取决于所使用的字符编码。
当使用 range 关键字遍历字符串时，迭代变量的类型是 rune，它是 Go 语言中专门用于表示 Unicode 字符的类型，实际上是一个 int32 类型的别名。 每次迭代，range 关键字会将字符串中的每个字符解码为一个 rune 类型的值，这样可以正确地处理 Unicode 字符。

77. 组合
    中等
    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
    你可以按 任何顺序 返回答案。
    示例 1：
    输入：n = 4, k = 2
    输出：
    [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
    ]
    示例 2：
    输入：n = 1, k = 1
    输出：[[1]]

func combine(n int, k int) [][]int {
   
	if k > n {
   
		return nil
	}

	var result [][]int
	var backtrace func(cur []int, index int)
	backtrace = func(cur []int, index int) {
   
		if len(cur) == k {
   
			temp := make([]int, k)
			copy(temp, cur)
			result = append(result, temp)
			return
		}

		//从当前的下一位数字开始遍历
        // 优化：剪枝，当剩余的数字个数不足以构成一个组合时，提前结束循环
		remaining := k - len(cur)
		for i := index; i <= n-remaining+1; i++ {
   
			backtrace(append(cur, i), i + 1)
		}
	}

	backtrace([]int{
   }, 1)
	return result
}

46. 全排列
    中等
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    示例 1：
    输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    示例 2：
    输入：nums = [0,1]
    输出：[[0,1],[1,0]]
    示例 3：
    输入：nums = [1]
    输出：[[1]]

func permute(nums []int) [][]int {
   
	n := len(nums)
	if n == 1 {
   
		return [][]int{
   {
   nums[0]}}
	}
	if n == 0 {
   
		return nil
	}

	var result [][]int
	var backtrace func(path []int)
	//使用一个数组来记录哪个数字被使用过
	used := make([]bool, n)

	backtrace = func(path []int) {
   
		//找到递归的某一个条件，返回
		if len(path) == n {
   
			temp := make([]int, n)
			copy(temp, path)
			result = append(result, temp)
			return
		}

		for i := 0; i < n; i++ {
   
			if !used[i] {
   
				//表示当前元素没有被选择，可以选择当前元素
				used[i] = true
				path = append(path, nums[i])

				//递归调用，处理下一个元素
				backtrace(path)

				//回溯，取消选择当前元素，是因为可能当前元素不符合，只能回溯选择其他
				//类似“单词搜索”，恢复元素
				used[i] = false
				path = path[:len(path)-1]
			}
		}
	}

	backtrace([]int{
   })
	return result
}

39. 组合总和
    中等
    相关标签
    相关企业
    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
    candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
    对于给定的输入，保证和为 target 的不同组合数少于 150 个。
    示例 1：
    输入：candidates = [2,3,6,7], target = 7
    输出：[[2,2,3],[7]]
    解释：
    2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
    7 也是一个候选， 7 = 7 。
    仅有这两种组合。
    示例 2：
    输入: candidates = [2,3,5], target = 8
    输出: [[2,2,2,2],[2,3,3],[3,5]]
    示例 3：
    输入: candidates = [2], target = 1
    输出: []

func combinationSum(candidates []int, target int) [][]int {
   
	var result [][]int
	var path []int

	// 排序是为了在回溯的过程中更容易剪枝
	sort.Ints(candidates)

	var backtrack func(index int, target int)
	backtrack = func(index int, target int) {
   
		if target == 0 {
   
			// 将当前路径添加到结果中
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}

		for i := index; i < len(candidates); i++ {
   
			// 大剪枝：如果当前元素大于剩余目标值，后续的元素都不可能满足条件，直接跳过
			if candidates[i] > target {
   
				//因为上面已经对数组进行排序，如果遇到数组中的值大于目标值，那么后续的值也会大于目标值，就需要跳出总循环
				break
			}

			// 剪枝：去重，跳过相邻相同的元素
			if i > index && candidates[i] == candidates[i-1] {
   
				continue
			}

			// 选择当前元素
			path = append(path, candidates[i])
			// 递归调用，继续选择，注意这里可以重复选择当前元素
			backtrack(i, target-candidates[i])
			// 回溯，取消选择当前元素，是因为可能当前元素不符合，只能回溯选择其他
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return result
}

40. 组合总和 II
    中等
    给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的每个数字在每个组合中只能使用 一次 。
    注意：解集不能包含重复的组合。
    示例 1:
    输入: candidates = [10,1,2,7,6,1,5], target = 8,
    输出:
    [
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
    ]
    示例 2:
    输入: candidates = [2,5,2,1,2], target = 5,
    输出:
    [
    [1,2,2],
    [5]
    ]

func combinationSum2(candidates []int, target int) [][]int {
   
	var result [][]int
	var path []int

	// 排序是为了在回溯的过程中更容易剪枝
	sort.Ints(candidates)

	var backtrack func(index int, target int)
	backtrack = func(index int, target int) {
   
		if target == 0 {
   
			// 将当前路径添加到结果中
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}

		for i := index; i < len(candidates); i++ {
   
			// 大剪枝：如果当前元素大于剩余目标值，后续的元素都不可能满足条件，直接跳过
			if candidates[i] > target {
   
				//因为上面已经对数组进行排序，如果遇到数组中的值大于目标值，那么后续的值也会大于目标值，就需要跳出总循环
				break
			}

			// 剪枝：去重，跳过相邻相同的元素
			if i > index && candidates[i] == candidates[i-1] {
   
				continue
			}

			// 选择当前元素
			path = append(path, candidates[i])
			// 递归调用，继续选择，注意这里不可以重复选择当前元素，所以对 i+1 的下标递归
			backtrack(i+1, target-candidates[i])
			// 回溯，取消选择当前元素，是因为可能当前元素不符合，只能回溯选择其他
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return result
}

39.组合总和 和 40.组合总和II，唯一的不同就是第39题可以重复使用，所以递归传值为：
backtrack(i, target-candidates[i])
第40题是数值不可以重复使用，因此递归传值为：
backtrack( i + 1, target-candidates[i])
其他代码全部一样

216. 组合总和 III
     中等
     找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
     只使用数字1到9
     每个数字 最多使用一次
     返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
     示例 1:
     输入: k = 3, n = 7
     输出: [[1,2,4]]
     解释:
     1 + 2 + 4 = 7
     没有其他符合的组合了。
     示例 2:
     输入: k = 3, n = 9
     输出: [[1,2,6], [1,3,5], [2,3,4]]
     解释:
     1 + 2 + 6 = 9
     1 + 3 + 5 = 9
     2 + 3 + 4 = 9
     没有其他符合的组合了。
     示例 3:
     输入: k = 4, n = 1
     输出: []
     解释: 不存在有效的组合。
     在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

func combinationSum3(k int, n int) [][]int {
   
	if k > n {
   
		return nil
	}
	result := [][]int{
   }
	path := []int{
   }

	var backtrack func(index int, target int)
	backtrack = func(index int, target int) {
   
		if len(path) == k && target == 0 {
   
			// 将当前路径添加到结果中
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}

		for i := index; i <= 9; i++ {
   
			if i > target {
   
				//因为上面已经对数组进行排序，如果遇到数组中的值大于目标值，那么后续的值也会大于目标值，就需要跳出总循环
				break
			}
			path = append(path, i)
			backtrack(i+1, target-i)
			path = path[:len(path)-1]
		}
	}

	backtrack(1, n)
	return result
}

22. 括号生成
    中等
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    示例 1：
    输入：n = 3
    输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
    示例 2：
    输入：n = 1
    输出：[“()”]

func generateParenthesis(n int) []string {
   
	var result []string
	var backtrack func(s string, left, right int)

	backtrack = func(s string, left, right int) {
   
		//括号对数为n,那么括号的个数就为2*n
		if len(s) == 2*n {
   
			result = append(result, s)
			return
		}

		if left < n {
   
			backtrack(s+"(", left+1, right)
		}
		if right < left {
   
			backtrack(s+")", left, right+1)
		}
	}
	backtrack("", 0, 0)
	return result
}