宣城建设网站,提升网站知名度,重庆市建设工程交易中心,论文 网站建设可行性子集Ⅱ
题目要求 解题思路
回溯法 一般情况下#xff0c;看到题目要求[所有可能的结果]#xff0c;而不是[结果的个数]#xff0c;我们就知道需要暴力搜索所有的可行解了#xff0c;可以使用[回溯法] 回溯法是一种算法思想#xff0c;而递归式一种编程方式#xff0c;回…子集Ⅱ
题目要求 解题思路
回溯法 一般情况下看到题目要求[所有可能的结果]而不是[结果的个数]我们就知道需要暴力搜索所有的可行解了可以使用[回溯法] 回溯法是一种算法思想而递归式一种编程方式回溯法可以使用递归来实现。 回溯法的整体思路是搜索每一条路每次回溯是对具体的一条路径而言的。对当前路径下的未探索区域进行搜索则可能出现两种情况 1.当前未搜索区域满足结束条件则保留当前路径并退出当前搜索 2.当前未搜索区域需要继续搜索则遍历当前所有可能的选择如果该选择符合要求则把当前选择加入当前的搜索路径中并继续搜索新的未探索区域。 上面说的未探索区域是指搜索某条路径时的未搜索区域并不是全局的未搜索区域。 回溯法搜所有可行解的模板一般是这样子的
res []
path []def backtrack(未搜索区域res,path):if path 满足条件res.add(path) # 深度拷贝# return # 如果不用继续搜索需要returnfor 选择 in 未探索区域当前可能的选择if 当前选择符合要求path.add(当前选择)backtrack(新的未探索区域res,path)path.pop()backtrack 的含义是未探索区域中到达结束条件的所有可能路径path 变量是保存的是一条路径res 变量保存的是所有搜索到的路径。所以当「未探索区域满足结束条件」时需要把 path 放到结果 res 中。 path.pop() 是啥意思呢它是编程实现上的一个要求即我们从始至终只用了一个变量 path所以当对 path 增加一个选择并 backtrack 之后需要清除当前的选择防止影响其他路径的搜索。
按照模板
1.未探索区域剩下的未探索的数组num[index:N-1] 2.每个path是否都满足条件任何一个path都是子集都满足条件都要放到res中 3.当前path满足条件时是否继续搜索是的找到num[0:index-1]中的子集之后num[index]添加到老的path中会形成新的子集 4.未探索区域当前可能的选择每次选择可以选取s的1个祖父即num[index] 5.当前选择符合要求任何num[index]都是符合要求的直接放到path中 6.新的未探索区域num在index之后的剩余字符串num[index1:N-1].
代码
res []nums.sort()self.dfs(nums, 0, res, [])return resdef dfs(self, nums, index, res, path):if path not in res:res.append(path)for i in range(index, len(nums)):if i index and nums[i] nums[i - 1]:continueself.dfs(nums, i 1, res, path [nums[i]])复杂度分析
时间复杂度: O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n)其中n是数组nums的长度。排序的时间复杂度未 O ( n l o n g n ) O(nlong n) O(nlongn)。最坏的情况下nums中无重复元素需要枚举其中所有 2 n 2^n 2n个子集每个子集加入答案时需要拷贝一份耗时 O ( n ) O(n) O(n)一共需要 O ( n ∗ 2 n ) O ( n ) O ( n ∗ 2 n ) O(n * 2^n) O(n) O(n * 2^n) O(n∗2n)O(n)O(n∗2n)的时间来构造子集。由于在渐进意义上 O ( n l o g n ) O(n log n) O(nlogn)小于 O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n)故总的时间复杂度为 O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n) 空间复杂度: O ( n ) O(n) O(n)临时数组t的空间代价是 O ( n ) O(n) O(n)递归时栈空间的代价为 O ( n ) O(n) O(n)
