题解 | 回溯法解决排列组合问题 #一、集合的所有子集（一) #

回溯法解决排列组合问题

模板

result=[]
def dfs(路径，选择列表）：
	if 满足结束条件：
		result.append(路径)
		return
	for 选择 in 选择列表：
		做选择
		dfs(路径，选择列表）
		撤销选择

一、NC27 集合的所有子集（一)

子集：元素无重不可复选

class Solution:
    def subsets(self , s: List[int]) -> List[List[int]]:
        # write code here
        def dfs(track,start):
            res.append(track.copy())
            for i in range(start,len(s)):
                # track记录访问过的元素
                track.append(s[i])
                dfs(track,i+1)
                track.pop() 
        # res收集所有子集，track记录访问过的元素
        res,track = [],[]
        s.sort()
        dfs(track,0)
        return res

二、NC358 组合

组合：元素无重不可复选

class Solution:
    def combine(self , n: int, k: int) -> List[List[int]]:
        # write code here
        def dfs(track,start):
            if len(track) == k:
                res.append(track.copy())
                return
            for i in range(start,n+1):
                track.append(i)
                dfs(track,i+1)
                track.pop()
        res,track = [],[]
        dfs(track,1)
        return res

三、N43 没有重复项数字的全排列

排列：元素无重不可复选

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(nums):
            if len(track)==len(num):
                res.append(track.copy())
                return
            for i in range(len(num)):
                if used[i]: 
                    continue
                used[i] = True
                track.append(nums[i])
                dfs(nums)
                track.pop()
                used[i] = False
        res,track = [], []
        used = [False] * len(num)
        dfs(num)
        return res

四、NC221 集合的所有子集(二)

和（一）一样，只不过加了约束条件： if track not in res: res.append(track.copy())

class Solution:
    def subsets(self , nums: List[int]) -> List[List[int]]:
        # write code here
        def dfs(track,start):
            if track not in res:
                res.append(track.copy())
            for i in range(start,len(nums)):
                track.append(nums[i])
                dfs(track,i+1)
                track.pop()
        res,track = [],[]
        nums.sort()
        dfs(track,0)
        return res

五、NC42 有重复项数字的全排列

也是换了停止条件：

if track not in res and len(track)==len(num):
                res.append(track.copy())
                Return

class Solution:
    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(track):
            if track not in res and len(track)==len(num):
                res.append(track.copy())
                return
            for i in range(len(num)):
                if used[i]:
                    continue
                used[i] = True
                track.append(num[i])
                dfs(track)
                track.pop()
                used[i] = False
        
        res, track = [],[]
        used = [False]*len(num)
        num.sort()
        dfs(track)
        return res

六、NC121 字符串的排列

变了结束条件

            if len(track)==len(s):#track:['a','a','b']/t ['a','b','a']/t ['b','a','a']
                tmp = "".join(track)
                if tmp not in res:#res:["aab","aba","baa"]
                    res.append(tmp)
                    return

class Solution:
    def Permutation(self , s: str) -> List[str]:
        # write code here
        def dfs(track):
            if len(track)==len(s):#track:['a','a','b']/t ['a','b','a']/t ['b','a','a']
                tmp = "".join(track)
                if tmp not in res:#res:["aab","aba","baa"]
                    res.append(tmp)
                    return
            for i in range(len(s)):
                if visited[i] :
                    continue
                visited[i] = True
                track.append(s[i])
                dfs(track)
                track.pop()
                visited[i] = False
        #s=list(s)
        track,res,tmp = [],[],[]
        visited = [False]*len(s) 
        dfs(track)
        return res

七、NC367 第K个n的排列

dfs函数不变

class Solution:
    def KthPermutation(self , n: int, k: int) -> str:
        # write code here
        def dfs(nums):
            if len(track)==len(num):
                tmp.append(track.copy())
                return
            for i in range(len(num)):
                if used[i]: 
                    continue
                used[i] = True
                track.append(nums[i])
                dfs(nums)
                track.pop()
                used[i] = False
        tmp,track = [], []
        num=[i for i in range(1,n+1)]
        used = [False] * len(num)
        dfs(num)
        res = [str(i) for i in tmp[k-1]] #"['1', '2', '4', '3', '5']"
        return ''.join(res)#"12435"

八、NC329 电话号码的字母组合

组合问题，只不过不是直接加入当前字符，而是加入当前字符对应的数字

class Solution:
    def phoneNumber(self , num: str) -> List[str]:
        # write code here
        def dfs(track,start):
            if len(track) == len(num):
                res.append(''.join(track))
                return
            for d in chars[num[start]]:
                #print(d)
                track.append(d)
                dfs(track,start+1)
                track.pop()

        chars = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9": "wxyz"}
        res,track= [],[]
        dfs(track,0)
        return res