Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】

输入: 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]]

def permuteUnique(nums):
    """
    使用回溯算法加剪枝生成数组的所有不重复全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有不重复的全排列
    """
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    nums.sort()  # 排序以方便剪枝
    res = []
    backtrack([], [False] * len(nums))
    return res
# 示例调用
print(permuteUnique([1, 1, 2]))  # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

def permuteUnique(nums):
    """
    使用字典序排列法生成数组的所有不重复全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有不重复的全排列
    """
    def next_permutation(nums):
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i == -1:
            nums.reverse()
            return False
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])
        return True
    nums.sort()
    res = [nums[:]]
    while next_permutation(nums):
        res.append(nums[:])
    return res
# 示例调用
print(permuteUnique([1, 1, 2]))  # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

def permuteUnique(nums):
    """
    使用递归交换方法生成数组的所有不重复全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有不重复的全排列
    """
    def backtrack(start):
        if start == len(nums):
            res.append(nums[:])
            return
        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    nums.sort()  # 排序以方便剪枝
    res = []
    backtrack(0)
    return res
# 示例调用
print(permuteUnique([1, 1, 2]))  # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

def permuteUnique(nums):
    """
    使用基于计数的回溯法生成数组的所有不重复全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有不重复的全排列
    """
    def backtrack(comb, counter):
        if len(comb) == len(nums):
            res.append(comb[:])
            return
        for num in counter:
            if counter[num] > 0:
                comb.append(num)
                counter[num] -= 1
                backtrack(comb, counter)
                comb.pop()
                counter[num] += 1
    counter = {}
    for num in nums:
        if num in counter:
            counter[num] += 1
        else:
            counter[num] = 1
    res = []
    backtrack([], counter)
    return res
# 示例调用
print(permuteUnique([1, 1, 2]))  # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

def permuteUnique(nums):
    """
    使用迭代法生成数组的所有不重复全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有不重复的全排列
    """
    perms = [[]]
    for num in nums:
        new_perms = []
        for perm in perms:
            for i in range(len(perm) + 1):
                new_perms.append(perm[:i] + [num] + perm[i:])
                if i < len(perm) and perm[i] == num:
                    break
        perms = new_perms
    return perms
# 示例调用
print(permuteUnique([1, 1, 2]))  # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]