• 回溯算法集合（全排列，组合，子集）

    一套模板搞定全排列，组合，子集问题（递归嵌套for循环）

    组合问题：leetcode77、leetcode39、leetcode40、leetcode216

    全排列问题：leetcode46、leetcode47

    子集问题：leetcode78、leetcode90

    基础模板

    1. def __init__(self):
    2.     #收集所有符合条件的集合
    3.     self.paths = []
    4.     #临时结果存放并需要回溯
    5.     self.path = []
    6. def backtracking(参数值)：
    7.     if 递归终止条件：
    8.         return
    9.     
    10.     for 循环：
    11.         self.path.append(元素)
    12.         backtracking(参数值)
    13.         self.path.pop()

     1.组合问题

    leetcode77:

    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

    你可以按 任何顺序 返回答案。

    解题关键：递归函数中的start_index参数用于防止元素选取重复

    1. class Solution:
    2.     def __init__(self):
    3.         self.paths = []
    4.         self.path = []
    5.     def combine(self, n: int, k: int) -> List[List[int]]:
    6.         def backtracking(n, k, start_index):
    7.             #递归终止条件
    8.             if len(self.path) == k:
    9.                 #将符合条件的临时集合加入到最终集合中
    10.                 self.paths.append(self.path[:])
    11.                 return
    12.             #start_index用于进行控制深度递归时，元素不会进行重复选取，
    13.             #而是从本轮递归选取的元素的下一个元素开始。n-(k-len(self.path))+2
    14.             #为剪枝操作，当元素从数组中最后几位开始选取时，后面的长度不足为k，故不需要再操作
    15.             for i in range(start_index, n-(k-len(self.path))+2):
    16.                 #加入元素
    17.                 self.path.append(i)
    18.                 #递归
    19.                 backtracking(n, k, i+1)
    20.                 #元素回溯，会弹出一个元素，进行下一个元素的选取
    21.                 self.path.pop()
    22.  
    23.         backtracking(n, k, 1)
    24.         return self.paths

    leetcode39:

    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

    candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。  

    对于给定的输入，保证和为 target 的不同组合数少于 150 个。

     

    解题关键：start_index在递归函数的变化，每一个元素可被重复选取，因此递归函数中start_index

    仍然为i。

    1. class Solution:
    2.     def __init__(self):
    3.         self.paths = []
    4.         self.path = []
    5.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    6.  
    7.         def backtracking(candidates, target, start_index):
    8.  
    9.             if target == 0:
    10.                 self.paths.append(self.path[:])
    11.                 return
    12.  
    13.             for i in range(start_index, len(candidates)):
    14.                 #剪枝，大于target的集合不需要再往后选取
    15.                 if target < 0:
    16.                     return
    17.                 
    18.                 #对每个元素做减法，与递归结束条件target==0呼应
    19.                 target -= candidates[i]
    20.                 self.path.append(candidates[i])
    21.                 #题目条件每个元素可以重复被选取，所以这里start_index仍然为i而不是i+1
    22.                 backtracking(candidates, target, i)
    23.                 self.path.pop()
    24.                 #对每个元素做加法，与递归结束条件target==0呼应
    25.                 target += candidates[i]
    26.  
    27.         backtracking(candidates, target, 0)
    28.         return self.paths

    leetcode40

    给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的每个数字在每个组合中只能使用 一次 。

    注意：解集不能包含重复的组合。 

    解题关键：数组中含有重复元素，每个元素不能重复使用，需要在选取过程中去重

    1. class Solution:
    2.     def __init__(self):
    3.         self.path = []
    4.         self.paths = []
    5.     def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    6.  
    7.         def backtracking(candidates, target, start_index):
    8.  
    9.             if target == 0:
    10.                 self.paths.append(self.path[:])
    11.                 return
    12.  
    13.             for i in range(start_index, len(candidates)):
    14.                 #剪枝
    15.                 if target < 0:
    16.                     return
    17.                 #存在重复元素，去重，这个前提条件是数组为有序
    18.                 if i > start_index and candidates[i] == candidates[i-1]:
    19.                     continue
    20.                 
    21.                 target -= candidates[i]
    22.                 self.path.append(candidates[i])
    23.                 #元素不可重复使用，start_index需为i+1，即从下一个元素开始选取
    24.                 backtracking(candidates, target, i+1)
    25.                 self.path.pop()
    26.                 target += candidates[i]
    27.  
    28.         #这里sorted()将数组元素排序，是去重操作的前提条件
    29.         backtracking(sorted(candidates), target, 0)
    30.  
    31.         return self.paths

     leetcode216

    找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

    只使用数字1到9
    每个数字 最多使用一次 
    返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

    1. class Solution:
    2.     def __init__(self):
    3.         self.path = []
    4.         self.paths = []
    5.     def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    6.  
    7.         def backtracking(k, n, start_index):
    8.  
    9.             if len(self.path) == k:
    10.                 #无论有没有符合条件的集合，都要结束递归，后面的递归超出条件k个，无意义
    11.                 if n == 0:
    12.                     self.paths.append(self.path[:])
    13.                 return
    14.             
    15.             for i in range(start_index, 9 - (k-len(self.path))+2):
    16.  
    17.                 if n < 0:
    18.                     return
    19.                 
    20.                 n -= i
    21.                 self.path.append(i)
    22.                 backtracking(k, n, i+1)
    23.                 self.path.pop()
    24.                 n += i
    25.  
    26.         backtracking(k, n, 1)
    27.         return self.paths

     

    2.全排列问题

    leetcode46

    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    1. class Solution:
    2.     def __init__(self):
    3.         self.paths = []
    4.         self.path = []
    5.     def permute(self, nums: List[int]) -> List[List[int]]:
    6.  
    7.         def backtracking(nums):
    8.  
    9.             if len(self.path) == len(nums):
    10.                 self.paths.append(self.path[:])
    11.                 return
    12.  
    13.             for i in range(0, len(nums)):
    14.                 #去掉含有重复元素的组合
    15.                 if nums[i] in self.path:
    16.                     continue
    17.  
    18.                 self.path.append(nums[i])
    19.                 #全排列有顺序的讲究，故每一次递归的遍历都可以从数组的第0个元素开始
    20.                 backtracking(nums)
    21.                 self.path.pop()
    22.  
    23.         backtracking(nums)
    24.         return self.paths

    leetcode47

    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

    1. class Solution:
    2.     def __init__(self):
    3.         self.path = []
    4.         self.paths = []
    5.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    6.         used = [0] * len(nums)
    7.         def backtracking(nums, used):
    8.  
    9.             if len(self.path) == len(nums):
    10.                 self.paths.append(self.path[:])
    11.                 return
    12.  
    13.             for i in range(0, len(nums)):
    14.                 #保证每个元素只可用一次
    15.                 if not used[i]:
    16.                     #去掉数组中因存在重复元素而形成的重复组合
    17.                     if i > 0 and nums[i]==nums[i-1] and not used[i-1]:
    18.                         continue
    19.                     #含有重复元素，需要记录每个元素的使用情况，并且作为递归函数的参数
    20.                     used[i] = 1
    21.                     self.path.append(nums[i])
    22.                     backtracking(nums, used)
    23.                     self.path.pop()
    24.                     used[i] = 0
    25.  
    26.         backtracking(sorted(nums), used)
    27.         return self.paths

    3.子集问题

    leetcode78

    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

    1. class Solution:
    2.     def __init__(self):
    3.         self.path = []
    4.         self.paths = []
    5.     def subsets(self, nums: List[int]) -> List[List[int]]:
    6.  
    7.         def backtracking(nums, start_index):
    8.  
    9.             #每加进来一个元素就做一次结果收集
    10.             self.paths.append(self.path[:])
    11.  
    12.             if len(self.path) == len(nums):
    13.                 return
    14.  
    15.             for i in range(start_index, len(nums)):
    16.  
    17.                 self.path.append(nums[i])
    18.                 #保证元素无重复选取，start_index为i+1
    19.                 backtracking(nums, i+1)
    20.                 self.path.pop()
    21.  
    22.         backtracking(nums, 0)
    23.         return self.paths

    leetcode90

    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

    解题关键：数组中有重复元素，需要去除因存在重复元素而形成的重复集合

    1. class Solution:
    2.     def __init__(self):
    3.         self.paths = []
    4.         self.path = []
    5.     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    6.  
    7.         def backtracking(nums, start_index):
    8.             self.paths.append(self.path[:])
    9.  
    10.             if len(self.path) == len(nums):
    11.                 return
    12.  
    13.             for i in range(start_index, len(nums)):
    14.                 
    15.                 #数组中有重复元素，需要去除因存在重复元素而形成的重复集合
    16.                 if i > start_index and nums[i] == nums[i-1]:
    17.                     continue
    18.  
    19.                 self.path.append(nums[i])
    20.                 backtracking(nums, i+1)
    21.                 self.path.pop()
    22.  
    23.         backtracking(sorted(nums), 0)
    24.         return self.paths

    参考文献：代码随想录

  • 相关阅读:
    汽车网络安全 -- ECU会遭受黑客怎样的攻击？
    [附源码]java毕业设计小型银行贷款管理系统
    默认路由配置
    Java.lang.Character类中codePointAt(CharSequence seq, int index)方法具有什么功能呢？
    Makefile——Linux下C/C++编译方法
    Visual Studio 中使用 CMake
    软考高级考试中有五大证书，哪个更值得考？
    制作频谱灯
    【React 报错】—Remove untracked files, stash or commit any changes, and try again.
    Merkle Tree 简介
  • 原文地址：https://blog.csdn.net/qq_44091004/article/details/127792558