【回溯法DFS】78. 子集1、90. 子集 II

2021/4/24 18:25:46

本文主要是介绍【回溯法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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程