基于Python数据结构之递归与回溯搜索-创新互联
目录
1. 递归函数与回溯深搜的基础知识
2. 求子集 (LeetCode 78)
3. 求子集2 (LeetCode 90)
4. 组合数之和(LeetCode 39,40)
5. 生成括号(LeetCode 22)
6. N皇后(LeetCode 51,52)
7. 火柴棍摆正方形(LeetCode 473)
1. 递归函数与回溯深搜的基础知识
递归是指在函数内部调用自身本身的方法。能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
2. 求子集 (LeetCode 78 Subsets)
2.1题目
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
2.2思路
初始化,[ ]的子集为[ [ ] ]
nums[ : n]的子集为所有nums[ : n-1]的子集 加上所有nums[ : n-1]的子集+元素nums[n-1]
2.3代码
class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ size = len(nums) return self.solve(nums, size) def solve(self, nums, n): if n == 0: return [[]] temp = self.solve(nums[:n-1], n-1) ans = temp[:] for i in temp: ans.append(i + [nums[n-1]]) return ans
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页标题:基于Python数据结构之递归与回溯搜索-创新互联
文章地址:http://scyanting.com/article/ddehho.html