回溯——7.子集II

力扣题目链接

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

• 输入: [1,2,2]
• 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

解题思路总结：

1. 排序：首先对数组进行排序，便于之后的重复元素跳过处理。
2. 回溯法：通过递归遍历所有可能的子集，并在每次递归中将当前路径加入结果集。
3. 去重：利用排序后的数组，结合 used 数组，通过条件 nums[i] == nums[i-1] 和 not used[i - 1]，来跳过同一层中重复的元素，从而避免生成重复子集。

完整代码如下：

class Solution:
    def subsetsWithDup(self, nums):
        result = []
        path = []
        used = [False] * len(nums)
        nums.sort()  # 去重需要排序
        self.backtracking(nums, 0, used, path, result)
        return result

    def backtracking(self, nums, startIndex, used, path, result):
        result.append(path[:])  # 收集子集
        for i in range(startIndex, len(nums)):
            # used[i - 1] == True，说明同一树枝 nums[i - 1] 使用过
            # used[i - 1] == False，说明同一树层 nums[i - 1] 使用过
            # 而我们要对同一树层使用过的元素进行跳过
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            path.append(nums[i])
            used[i] = True
            self.backtracking(nums, i + 1, used, path, result)
            used[i] = False
            path.pop()

def subsetsWithDup(self, nums):
    result = []
    path = []
    used = [False] * len(nums)
    nums.sort()  # 去重需要排序
    self.backtracking(nums, 0, used, path, result)
    return result

• result：用于存储所有不重复的子集。
• path：用于存储当前正在构建的子集。
• used：这是一个布尔数组，用来标记数组中的每个元素是否已经在当前路径（path）中使用过。
• nums.sort()：在处理重复元素时，排序是必须的，因为只有在数组有序的情况下，才能通过简单的条件判断去除重复子集。

def backtracking(self, nums, startIndex, used, path, result):
    result.append(path[:])  # 收集子集

• backtracking 函数是回溯算法的核心。
• startIndex：控制下一步递归从哪里开始选择元素。
• 每次递归时，当前的 path（表示当前正在构建的子集）会被复制并加入到 result 中，表示我们收集了一个子集。

for i in range(startIndex, len(nums)):
    # used[i - 1] == True，说明同一树枝 nums[i - 1] 使用过
    # used[i - 1] == False，说明同一树层 nums[i - 1] 使用过
    # 而我们要对同一树层使用过的元素进行跳过
    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
        continue

• 这里的 for 循环遍历数组的每一个元素，从 startIndex 开始。
• if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]：这个条件判断用于跳过重复的元素，以避免生成重复的子集。具体解释如下：
  • i > 0：确保访问 nums[i-1] 时不会越界。
  • nums[i] == nums[i - 1]：如果当前元素和前一个元素相同，则可能会生成重复子集。
  • not used[i - 1]：前一个元素如果在同一层中没有被使用过（即没有在当前路径中被选择），则说明我们在当前层次中遇到了重复元素，此时应该跳过，以防止生成重复子集。

    path.append(nums[i])
    used[i] = True
    self.backtracking(nums, i + 1, used, path, result)
    used[i] = False
    path.pop()

• path.append(nums[i])：将当前元素加入到当前路径中。
• used[i] = True：标记当前元素已经在当前路径中使用。
• self.backtracking(nums, i + 1, used, path, result)：递归调用，开始从下一个索引 i + 1 继续构造子集。
• used[i] = False：回溯后，将当前元素标记为未使用，以便在其他路径中使用。
• path.pop()：回溯的关键步骤，撤销之前的选择，恢复状态，以便继续构造其他子集。