算法套路十一 ——回溯法之组合型回溯

• 该节是在上一节回溯法之子集型回溯的基础上进行描写，组合型回溯会在子集型回溯的基础上判断所选子集是否符合组合要求， 故请首先阅读上一节算法套路十——回溯法之子集型回溯

算法示例：LeetCode77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

可以按照上一节子集型回溯的想法分为两种思路，不过组合型回溯的区别在于对子集是否加入ans中有限制，如本题就要求子集中的个数为2，因此需要在递归时判断子集的个数，由此可在递归时判断并进行剪枝。

剪枝：对于本题，为考虑方便，我们可以从n开始进行选择，设path长为m，那么还需要选d=k - m个数设当前需要从[1,i]这i个数中选数，如果i<d，最后必然无法选出k个数不需要继续递归，如上图右边的图，k=3，如果我们目前选择的是2，且为避免重复，我们之后选择的数都要比2小，那可知不可能满足k=3，所以该递归路径可以直接结束。

法一：选或不选

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []path = []def dfs(i: int) -> None:d = k - len(path)  # 还要选 d 个数if d == 0:ans.append(path.copy())return# 不选 iif i > d: dfs(i - 1)# 选 ipath.append(i)dfs(i - 1)path.pop()dfs(n)return ans

法二：枚举下一个数选哪个

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []path = []def dfs(i: int) -> None:d = k - len(path)  # 还要选 d 个数if d == 0:ans.append(path.copy())returnfor j in range(i, d - 1, -1):path.append(j)dfs(j - 1)path.pop()dfs(n)return ans

算法练习一：LeetCode216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：只使用数字1到9，每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

此题可以在上一题的代码基础上修改，上一题已将所有选择k个数的集合返回，故本题只需在代码返回时判断当前组合之和是否为n，并且若总和大于n，即可直接退出递归进行剪枝

法一：选或不选

func combinationSum3(k int, n int) (ans [][]int){path := []int{}var dfs func(int)dfs = func(i int) {d := k - len(path) // 还要选 d 个数if d == 0 && sum(path)==n{ans = append(ans, append([]int(nil), path...))return}else if d<0||sum(path)>n{return}// 不选 iif i > d {dfs(i - 1)}// 选 ipath = append(path, i)dfs(i - 1)path = path[:len(path)-1]}dfs(9)return
}
func sum(nums []int)int{ans:=0for _,num:=range nums{ans+=num}return ans
}

法二：枚举下一个数选哪个

func combinationSum3(k int, n int) (ans [][]int){path := []int{}var dfs func(int)dfs = func(i int) {d := k - len(path) // 还要选 d 个数if d == 0 &&sum(path)==n{ans = append(ans, append([]int(nil), path...))return}else if d<0||sum(path)>n{return}for j := i; j >= d; j-- {path = append(path, j)dfs(j - 1)path = path[:len(path)-1]}}dfs(9)return
}
func sum(nums []int)int{ans:=0for _,num:=range nums{ans+=num}return ans
}

算法练习二：LeetCode22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

此题我们可以选择选或不选的思路，选择即是左括号，不选则表示为右括号，且分别用left与right记录当前生成的左括号与右括号个数，如果right>left，那么说明右括号比左括号还多，不符合要求，故直接返回。用m=2*n来记录当前长度，只有当递归到m时即可添加到ans中。对于选或不选直接记录，递归，回溯三步完成。

func generateParenthesis(n int) (ans []string) {cur:=[]byte{}m:=2*nleft,right:=0,0var dfs func(int)dfs=func(i int){if i==m{ans=append(ans,string(cur))return}if right>left{return}//选左括号if left<n{left++cur=append(cur,'(')dfs(i+1)cur=cur[:len(cur)-1]left--}//选右括号right++cur=append(cur,')')dfs(i+1)cur=cur[:len(cur)-1]right--}dfs(0)return 
}

算法练习三：LeetCode301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。1 <= s.length <= 25，s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成，s 中至多含 20 个括号

本题题目是删除无效的括号，但可以改变思路，与上题一样，可以考虑从字符串s中选择字符以满足括号有效，同样使用left与right记录当前选择的左括号与右括号个数，用letter记录字母的个数，且因为要删除最小数量的无效括号，可以考虑将所有有效的括号用ans记录，并利用maxLen记录满足条件的最长字符串，这样就之后删除最少的无效括号，之后使用函数findUniqueStrings来找出记录的所有满足条件的ans中长度为maxLen的字符串，且消除重复的字符串。

func removeInvalidParentheses(s string) (ans []string) {left,right,letter:=0,0,0cur:=[]byte{}maxLen:=-1n:=len(s)var dfs func(i int)dfs=func(i int){if i==n&&right==left{ans=append(ans,string(cur))//记录删除最少的括号后的长度maxLen=max(maxLen,left+letter+right)return}else if i==n||right>left{return}if s[i]=='('{//左括号不添加dfs(i+1)//左括号添加left++cur=append(cur,'(')dfs(i+1)cur=cur[:len(cur)-1]left--}else if s[i]==')'{if(left>right){//右括号添加right++cur=append(cur,')')dfs(i+1)cur=cur[:len(cur)-1]right--}//右括号不添加dfs(i+1)}else{//添加字母cur=append(cur,s[i])letter++dfs(i+1)letter--cur=cur[:len(cur)-1]}}dfs(0)if len(ans)==0{return []string{""}}return findUniqueStrings(ans,maxLen)
}
//找出最长的字符串，即删除最小括号，且去掉重复字符串
func findUniqueStrings(s []string, n int) []string {uniqueMap := make(map[string]bool)for i := 0; i < len(s); i++ {if len(s[i]) == n {uniqueMap[s[i]] = true}}uniqueStrings := make([]string, 0, len(uniqueMap))for unique := range uniqueMap {uniqueStrings = append(uniqueStrings, unique)}return uniqueStrings
}
func max(a,b int)int{if a>b{return a};return b}