子集-组合问题

2021年6月20日 11点热度 0条评论 来源: cyz0202

leetcode78-组合问题
leetcode39-子集问题

LC78子集问题
  • 题目一
  • 解法
    • 思想:迭代、递归/回溯
    • 迭代法:思想是,每增加一个数,新增加的子集跟已有子集关系密切,具体如下
      • 令nums=[0,1,2],观察[0,1]增加2后子集的变化
      • nums的子集为[ [ ], [0], [1], [0, 1], [2], [0,2], [1,2], [0,1,2] ]
      • 令nums1=[0,1],子集为[ [ ], [0], [1], [0,1] ],与nums子集非黄色部分一样
      • 观察nums1的子集和nums黄色部分子集,可以发现,nums1子集每个list元素加入2即得到黄色部分子集;
      • 因此得到迭代公式 subset([0,1]) + [2] = subset([0,1,2]);同理subset([0]) + [1] = subset([0,1])
    • 迭代法代码如下:
    """ 迭代方法:利用归纳思想,举例如下,{}用于提示读者注意迭代部分所在 nums=[1,2,3] [] [], {[1]} # 注意[1] 是 [] + [1] 得到 [], [1], {[2], [1,2]} # 注意[2],[1,2] 是 [] + [2] 和 [1] + [2]得到 [], [1], [2], [1,2], {[3], [1,3], [2,3], [1,2,3]} """
    def subsets(self, nums: List[int]) -> List[List[int]]:
    	res = [[]]
    	for num in nums:
    		res += [r + [num] for r in res]
    	return res
    
    • 递归/回溯法:思想是较长的子集是由较短的子集逐步添加元素构成的,具体如下
      • 令nums=[0,1,2,3]
      • 初始最短的子集为[ ],
      • 接下来是包含1个元素的子集,为[0], [1], [2], [3]
      • 接下来是包含2个元素的子集,以[0],[1]出发举例
        • 对于[0],其包含2个元素子集为 [0,1], [0,2], [0,3];
        • 对于[1],其包含2个元素子集为[1,2], [1,3];
        • 可以发现,[0]和[1]都是在从后一个元素开始添加元素构成新的子集,这时就可以大概知道如何递归了,即在当前已有子集基础上,遍历添加后续所有元素,即可得到增加一个元素的新的子集;
      • 值得一提的是,回溯体现在上述递归中还有遍历存在,如[0]递归得到[0,1],然后又递归得到[0,2],可视为[0,1]去掉[1]得到[0](故称为回溯)后添加[2]才得到的[0,2]
    • 递归法代码如下
    def subsets(self, nums: List[int]) -> List[List[int]]:
    	""" 回溯/递归方法:不断增加index及res_list nums=[1,2,3,4] [] [1]... [1,2],[1,3],[1,4]... [1,2,3],[1,2,4]... """
    	res = []
    	if not nums:
    		return res
    	n = len(nums)
    	
    	# 创建递归函数,是递归方法典型的写法
    	def helper(i, tmp):
    		res.append(tmp)
    		for j in range(i, n):
    			helper(j+1, r + [nums[j])
    			
    	helper(0, [])
    	return res
    
LC39组合问题
  • 题目二
  • 解法:
    • 思想:递归,该题思路比较浅显,由于可取重复元素,因此稍微麻烦一点;
      • 具体的,第一点是结果集合不能重复,因此一个思想是类似上一题解法二,有个index逐渐增加,控制重复出现
      • 第二点,由于是可重复取同一元素,因此,排序后,每次取一个元素c,得到新的target_new = target - c,然后判断是否继续取c,还是取更大的(已排序)元素;该部分是递归的主要部分,有新的target_new,有新的可取元素的index,就可以重复前面的工作;
    • 递归代码如下:
    class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """ 迭代/递归方法 C = [2,3,5] T = 8 3种情况:来自[2,3,5];来自[3,5];来自[5] 以[2,3,5]举例 [2]&T=6 # 取2,新的target=6 [2,2]&T=4, [2,3]&T=3, [2,5]&T=1 [2,2,2]&T=2, [2,2,3]&T=1, [2,2,5X]... [2,2,2,2], [2,2,3,2X]... """
        if not candidates:  # [] or None
            return []
        res = []
        len_c = len(candidates)
        candidates.sort()
    
        # 构造递归函数
        def helper(i, target):
        	# 递归终止条件
            if candidates[i] > target:  # 2 > 1,没有后续选择
                return []
            elif candidates[i] == target:  # 一个选择
                return [[candidates[i]]]
            
            c = candidates[i]
            res_list = []
            
            # 逐渐增加以便控制重复
            for j in range(i, len_c):
                if candidates[j] <= target - c:
                    sub_res_list = helper(j, target-c)
                    for sr in sub_res_list:
                    	# 将返回的子结果累积
                        res_list.append([c] + sr)
                else:
                    break
            return res_list
        
        for i in range(len_c):
            res.extend(helper(i, target))
        
        return res
        
    
    原文作者:cyz0202
    原文地址: https://blog.csdn.net/cyz0202/article/details/113753269
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。