全排列/ 全排列ii/ 子集/ 子集ii

2021年9月6日 1点热度 0条评论 来源: 向天抡大锤

文章目录

回溯法介绍

  • 基本思想:从一条路往前走,能进则进,不能进就退回来,换一条路进;
  • 遇到某类可以分解的问题,但是不能得出明确的动态规划或是递归解法,考虑回溯法;
  • 回溯法程序结构明确,可读性强,通过对问题的分析可以提高运行效率;但是在有明确递推公式求解的问题,使用回溯,效率很低;
  • 回溯法使用:将问题转化,构造出状态空间树,这棵树的每条路径都代表了一种可能的解;枚举每种可能的解的情况,得出结果;但是,回溯法中有一个约束函数,通过将约束函数和每个解对照,剔除不可能的解,节省时间;
    • 概念一:约束函数,根据题意定义,用于去除不合法的解,从为避免继续搜索该不合法解的剩余部分,约束函数对状态空间树的节点都有效;
    • 概念二:状态空间树,对所有解的图形描述,树上的每个子节点的解和父节点只有一个不同;
    • 概念三:1、扩展结点:一个正在生成孩子的结点。
      2、活结点:一个自身已生成,但孩子还没有全部生成的结点。
      3、死结点:一个所有孩子都已经生成的结点。
      4、子孙:结点E的子树上所有结点都是E的子孙。
      5、祖宗:从结点E到树根路径上的所有结点都是E的祖宗。
  • 解题步骤
    首先,要通过读题完成下面三个步骤:
    (1)描述解的形式,定义一个解空间,它包含问题的所有解。
    (2)构造状态空间树。
    (3)构造约束函数(用于杀死节点)。
  • 标准回溯模板
    # 回溯算法,复杂度较高,因为回溯算法就是暴力穷举,遍历整颗决策树是不可避免的
    res = []
    def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果.append(路径)
        return
    for 选择 in 选择列表:    # 核心代码段
        做出选择
        递归执行backtrack
        撤销选择
    
  • 排列场景回溯模板
    • 回溯模板1(不包括重复元素—参考全排列):主函数调用回溯帮助函数,return结果;
      回溯帮助函数: if(满足条件){return} for(所有元素){放入集合 调用回溯帮助函数 放出集合}
    • 回溯模板2(包括重复元素—参考全排列ii):主函数调用回溯帮助函数,return结果
      回溯帮助函数: if(满足条件){return} for(所有元素){判断重复使用数组是否置1 else:标记置1 放入集合 调用回溯帮助函数 放出集合 标记置0}

1、全排列

问题

给定一个 没有重复 数字的序列,返回其所有可能的全排列。
输入: [1,2,3]
输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

思路

回溯算法:先固定第一位(1),再固定第二位(2),第三位只能是(3);接下来第一位仍然为(1),第二位是(3),第三位是(2);此处属于不包括重复元素的回溯法
下图中每一条路径为全排列的结果

代码实现

def permute(nums):
	res = []
	def backtrace(nums, tmp):
		if not nums:
			res.append(tmp)
			return
		for i in range(len(nums)):
			backtrace(nums[:i] + nums[i + i:], tmp + [nums[i]])
	backtrace(nums, [])
	return res
	

2、全排列ii

问题

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
输入:nums = [1,1,2]
输出:[[1,1,2], [1,2,1], [2,1,1]]
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路

  • 属于包含重复数字的回溯法的应用;
  • 全排列之后去重,思路简单但把多余的情况也计算了。如何直接跳过重复的情况不去计算呢?:对同一个树枝上的数据去重,去重的首要是排序
  • 通过一个visited列表来记录该位置的元素,如果该位置已经被该元素“占领”过,例如[1,1,2] 当第一个“1” 在列表第一位中占位后,第二个“1”占领第一位的情况就无需考虑了,因为第一个“1”已经将所有的情况全都回溯掉了。
    在函数中创建visited列表,在每次递归的过程中都会创建一个新的列表,实际的作用就是用来当前的组合下,没有相同的nums[i]被重复排列。

代码实现

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    	nums.sort()
        res = []
        def backtrace(nums, temp):
            visited = []
            if not nums and temp not in res:
                res.append(temp)
                return
            for i in range(len(nums)):
                if nums[i] not in visited:
                    visited.append(nums[i])
                    backtrace(nums[:i] + nums[i + 1:], temp + [nums[i]])

        backtrace(nums, [])
        return res

3、子集

问题

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入:nums = [0]
输出:[[],[0]]

思路

代码实现

    def subsets(nums):
        res = []
        def backtrack(nums, tmp):
            res.append(tmp)
            for i in range(len(nums)):
                backtrack(nums[i+1:], tmp+[nums[i]])
        backtrack(nums, [])
        return res

4、子集ii

问题

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
输入: [1,2,2]
输出:
[[2],[1],[1,2,2],[2,2],[1,2],[]]

思路

还是去重!!!排序!!!

代码实现

def subsetsWithDup(nums):
	nums.sort()
	res = []
	def backtrace(nums, temp):
		visited = []
		res.append(temp)
		for i in range(len(nums)):
			if nums[i] not in visited:
				visited.append(nums[i])
				backtrace(nums[i+1:], temp + [nums[i]])
	backtrace(nums, [])
	return res

5、数据排列

    原文作者:向天抡大锤
    原文地址: https://blog.csdn.net/m0_54790354/article/details/113248803
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。