赞
踩
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] path = [] n = len(nums) def backtracking(nums, n): if len(path) == n: res.append(path[:]) return for i in range(n): # 因为没重复元素,所以只需判断当前元素是 # 否在path数组中即可,不用used数组 if nums[i] not in path: path.append(nums[i]) backtracking(nums, n) path.pop() else: continue backtracking(nums, n) return res
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def backtracking(nums, used): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i >= 1 and nums[i] == nums[i-1] and not used [i-1]: continue used[i] = 1 path.append(nums[i]) backtracking(nums, used) path.pop() used[i] = 0 res = [] path = [] nums.sort() # used 初始化都是零,含义:在nums数组中没有元素被使用 # used = [1, 0, 1,] 含义:nums[0],nums[2]已经被使用 used = [0 for i in range(len(nums))] backtracking(nums, used) return res
关于python内置的全排列,组合库
product 笛卡尔积 (有放回抽样排列)
就是nums中元素可以重复使用
permutations 排列 (不放回抽样排列)
nums中元素不可重复使用
combinations 组合,没有重复 (不放回抽样组合)
nums中元素不可重复使用
combinations_with_replacement 组合,有重复 (有放回抽样组合)
nums中元素可以重复使用
专业的解释还是要看官方啦:https://docs.python.org/3.10/library/itertools.html
""" 每个函数都有两参数, 第一个是可迭代对象, 第二个是要从可迭代对象中抽取出来进行 排列 或 组合 的元素个数 """ import itertools # lis 无重复元素 lis = ['a', 'b', 'c'] # 有放回排序(元素可以重复使用) for i in itertools.product(lis, repeat=2): print(i, end=' ') """ 有放回排序(元素可以重复使用): ('a', 'a') ('a', 'b') ('a', 'c') ('b', 'a') ('b', 'b') ('b', 'c') ('c', 'a') ('c', 'b') ('c', 'c') """ # 无放回排序(元素不可以重复使用) for i in itertools.permutations(lis, 2): print(i, end=' ') """ 无放回排序(元素不可以重复使用): ('a', 'b') ('a', 'c') ('b', 'a') ('b', 'c') ('c', 'a') ('c', 'b') """ # 无放回组合(元素不可以重复使用) for i in itertools.combinations(lis, 2): print(i, end=' ') """ 无放回组合(元素不可以重复使用): ('a', 'b') ('a', 'c') ('b', 'c') """ # 有放回组合(元素可以重复使用) for i in itertools.combinations_with_replacement(lis, 2): print(i, end=' ') """ 有放回组合(元素可以重复使用): ('a', 'a') ('a', 'b') ('a', 'c') ('b', 'b') ('b', 'c') ('c', 'c') """ # lis2 中有重复元素 lis2 = ['a', 'a', 'c'] # 有放回排序(元素可以重复使用) for i in itertools.product(lis2, repeat=2): print(i, end=' ') """ 有放回排序(元素可以重复使用): (这个a比较多为了解释,输出顺序进行了调整) ('a', 'a')(第一个a是下标为0的a,第二个a是下标为0的a) ('a', 'a')(第一个a是下标为0的a,第二个a是下标为1的a) ('a', 'a')(第一个a是下标为1的a,第二个a是下标为0的a) ('a', 'a')(第一个a是下标为1的a,第二个a是下标为1的a) ('a', 'c') ('a', 'c') (情况与上面类似) ('c', 'a') ('c', 'a') ('c', 'c') """ # 无放回排序(元素不可以重复使用) for i in itertools.permutations(lis2, 2): print(i, end=' ') """ 无放回排序(元素不可以重复使用): ('a', 'a') ('a', 'c') ('a', 'a') ('a', 'c') ('c', 'a') ('c', 'a') """ # 无放回组合(元素不可以重复使用) for i in itertools.combinations(lis2, 2): print(i, end=' ') """ 无放回组合(元素不可以重复使用): ('a', 'a') ('a', 'c') ('a', 'c') """ # 有放回组合(元素可以重复使用) for i in itertools.combinations_with_replacement(lis2, 2): print(i, end=' ') """ 有放回组合(元素可以重复使用): ('a', 'a') ('a', 'a') ('a', 'c') ('a', 'a') ('a', 'c') ('c', 'c') """
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。