回溯——7.子集II
力扣题目链接
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
解题思路总结：
- 排序：首先对数组进行排序，便于之后的重复元素跳过处理。
- 回溯法：通过递归遍历所有可能的子集，并在每次递归中将当前路径加入结果集。
- 去重：利用排序后的数组，结合
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 resultdef 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]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.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] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.pop()
path.append(nums[i])：将当前元素加入到当前路径中。used[i] = True：标记当前元素已经在当前路径中使用。self.backtracking(nums, i + 1, used, path, result)：递归调用，开始从下一个索引i + 1继续构造子集。used[i] = False：回溯后，将当前元素标记为未使用，以便在其他路径中使用。path.pop()：回溯的关键步骤，撤销之前的选择，恢复状态，以便继续构造其他子集。