LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll

输入: nums = [1,2,2]
输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

def subsetsWithDup(nums):
    """
    使用回溯法生成所有可能的子集，处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()  # 排序以方便处理重复元素
    results = []
    def backtrack(start, path):
        results.append(path[:])  # 添加当前子集
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue  # 跳过重复元素
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

def subsetsWithDup(nums):
    """
    使用迭代法生成所有可能的子集，处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    start, end = 0, 0
    for i in range(len(nums)):
        start = 0
        # 如果当前数字和前一个数字相同，则只在上一轮新加入的子集基础上追加
        if i > 0 and nums[i] == nums[i-1]:
            start = end + 1
        end = len(results) - 1
        for j in range(start, len(results)):
            results.append(results[j] + [nums[i]])
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

def subsetsWithDup(nums):
    """
    使用位掩码法生成所有可能的子集，并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = []
    seen = set()
    n = len(nums)
    for i in range(1 << n):  # 从 0 到 2^n - 1
        subset = []
        for j in range(n):
            if i & (1 << j):  # 检查第 j 位是否为 1
                subset.append(nums[j])
        # 转换成元组检查是否重复
        subset_tuple = tuple(subset)
        if subset_tuple not in seen:
            seen.add(subset_tuple)
            results.append(subset)
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

def subsetsWithDup(nums):
    """
    动态规划法生成所有可能的子集，并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    last_count = 0
    for i in range(len(nums)):
        start = last_count if i > 0 and nums[i] == nums[i-1] else 0
        last_count = len(results)
        results += [r + [nums[i]] for r in results[start:]]
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]