再谈全排列

2024-09-06 00:44
文章标签 排列 谈全

本文主要是介绍再谈全排列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接: . - 力扣(LeetCode)

每次做全排列的题目,我都要孕育好一阵子,到底怎么去思考这个问题呢?

首先,我觉得最好的方式就是画个树。

画了树之后,你就知道,这个问题,是一个循环遍历的问题,但是再遍历的过程中,你需要基于过去的状态(哪些元素被存储了),改变你之后的行为。

此外。我们还需要考虑终止条件,然后,这是一个回溯的问题,那么你需要考虑的就是回溯之后需要怎样的处理。

我们来一一回答这些问题

1. 如果保存过去的状态

我们可以通过一个mask,来记录哪些元素被传入了。

2. 如何设定终止条件

我们可以判断list的长度,如果list的长度和原数组一致,我们就可以保存。

3. backtrack之后的状态重置

我们需要重置两个状态,一个是path中的元素,另一个是遍历到的元素的判断。

class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""path = []result = []def backtrack(nums, used):if(len(path) == len(nums)):result.append(path[:])returnfor i,ele in enumerate(nums):if(used[i] == False):path.append(ele)used[i] = True            backtrack(nums,used)path.pop()used[i] = Falsereturn result used = [False] * len(nums)result = backtrack(nums, used)return result

这篇关于再谈全排列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140515

相关文章

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序

C++解决:求排列数

描述 输入两个整数m,n,求m个数字中选n个数的排列数。(1<=n<=m<=50) 输入描述 两个正整数m和n。 输出描述 一个正整数表示排列数。 用例输入 1  6 5 用例输出 1  720 AC code #include<bits/stdc++.h>using namespace std;int fun(int n) {int sum=1;for(int i=n

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

Leetcode刷题笔记:全排列

这是一个经典的回溯问题,下面是一个C++版本的解法: class Solution {public:void backtrack(vector<vector<int>>& res, vector<int>& nums, int start) {// 如果start到达nums的末尾,说明已经生成一个完整的排列if (start == nums.size()) {res.push_back(

PCB过孔规则排列,还是随机?

在现代电子设备设计中,印刷电路板(PCB)的复杂性不断增加,尤其是在高密度集成电路和多层PCB中,过孔(Via)起到了至关重要的作用。过孔通过将PCB的不同层相互连接,使得电路板不再局限于平面的布线,而是实现了立体化的电气连接结构,从而提升了设计的灵活性和电气性能。 1. 过孔的定义与作用 过孔,顾名思义,是PCB板上的一种孔,用于连接PCB不同层之间的导电路径。由于单层PCB的布线空间有限

HTML 无序排列 有序排列 框架

HTML 无序排列  有序排列 : <html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title> 第四讲代码汇总</title></head><!--margin-left 对象左边外延边距 (margin-left:5px; 左边外延距离5px)margin-ri

算法笔记03--归纳法之生成排列

生成排列 生成排列即对n个数的全排列,显然时间复杂度是n指数级的O(n^k) 假定可以生成n-1个数的所有排列,那么就可以扩展生成1,2,.....,n的排列。 例如1的生成排列即1 1,2的生成排列即1,2和2,1 1,2,3的生成排列在1,2的生成排列基础上可以这样得到: 1在第1位,2,3的生成排列 2在第1位,1,3的生成排列 3在第1位,2,3的生成排列 那么推广到1,