本文主要是介绍【回溯法DFS】78. 子集1、90. 子集 II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 78. 子集1
- leetcode: [问题详情](https://leetcode-cn.com/problems/subsets/).
- b站: [视频详解](https://www.bilibili.com/video/BV1HD4y1Q7Te).
- 方法一、回溯法
- 90. 子集 II
- leetcode: [问题详情](https://leetcode-cn.com/problems/subsets-ii/).
- b站: [视频详解](https://www.bilibili.com/video/BV11z4y1Q7Hd).
- 方法一、回溯法+剪枝
78. 子集1
leetcode: 问题详情.
b站: 视频详解.
方法一、回溯法
class Solution(object):
def subsets(self, nums):
def backtracking(start_index, nums, path, res):
res.append(copy.deepcopy(path)) # 让[]也加入res
for i in range(start_index, len(nums)):
path.append(nums[i])
backtracking(i+1, nums, path, res)
path.pop()
if not nums:
return []
res = []
path = []
start_index = 0
backtracking(start_index, nums, path, res)
return res
90. 子集 II
leetcode: 问题详情.
b站: 视频详解.
方法一、回溯法+剪枝
class Solution(object):
def subsetsWithDup(self, nums):
def backtracking(start_index, res, path):
res.append(copy.deepcopy(path))
for i in range(start_index, len(nums)):
if i>start_index and nums[i] == nums[i-1]: # 剪枝
continue
path.append(nums[i])
backtracking(i+1, res, path)
path.pop()
start_index = 0
res = []
path = []
nums.sort()
backtracking(start_index, res, path)
return res
这篇关于【回溯法DFS】78. 子集1、90. 子集 II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!