前言

继续归纳回溯算法
本篇是对子集、排列、组合的实践

1、子集

leet上78题

给定一组不含重复元素的整数数组 nums
返回该数组所有可能的子集（幂集）

套用模板

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []n = len(nums)def backtrack(i, tmp):res.append(tmp)for j in range(i, n):backtrack(j+1, tmp+[nums[j]])backtrack(0,[])return res

变种
nums含有重复元素
剪枝即可

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:res = []n = len(nums)nums.sort()def backtrack(i, tmp):res.append(tmp)for j in range(i, n):if j > i and nums[j] == nums[j-1]:continuebacktrack(j + 1, tmp + [nums[j]])backtrack(0, [])return res

2、排列

leet上46题

给定一个没有重复数字的序列
返回其所有可能的全排列

套用框架

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []def backtrack(nums, tmp):if not nums:res.append(tmp)returnfor i in range(len(nums)):backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])backtrack(nums, [])return res

变种
原数组有重复数
剪枝

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:res = []def backtrack(nums, tmp):if not nums:res.append(tmp)returnfor i in range(len(nums)):if nums[i] in nums[:i]:continuebacktrack(nums[:i] + nums[i+1:], tmp + [nums[i]])backtrack(nums, [])return res

3、组合

leet上77题

给定两个整数 n 和 k
返回 1 ... n 中所有可能的 k 个数的组合

套用框架

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:res = []def backtrack(i, k, tmp):if k == 0:res.append(tmp)returnfor j in range(i, n+1):backtrack(j+1, k-1, tmp+[j])backtrack(1, k, [])return res

结语

套用框架
剪枝