标题有点绕,详细点说就是:现在有一个集合,里面存在重复的元素,怎样获得其所有子集,且保证子集中没有重复的集合。举例:集合[1, 1]中所有互不相同的子集集合为[[], [1], [1, 1]],其中[1]出现了两次,因此只保留一个。

首先先从最简单的开始,不考虑子集重复的话,怎样获得一个集合的所有子集?

很自然想到DFS。每一步分为两个集合,已选择的集合和待分配的集合,依次将待分配的集合中的元素分配至已选择的集合中,该元素之后的所有元素的集合构成新的待分配的元素的集合。

示例集合:arr = [1, 2, 2, 3],下同

代码如下:

# get all subset of arr

def dfs(arr, start, path, res):
    res.append(path)
    for i in range(start, len(arr)):
        dfs(arr, i + 1, path + [arr[i]], res)

def get_subset(arr):
    res = []
    dfs(arr, 0, [], res)
    return res

arr = [1, 2, 2, 3]
get_subset(arr)

为方便理解,画出DFS步骤图:

可以发现,蓝色圈圈出的两处存在重复,而这种重复,源自选择分配阶段,向已选择的集合中放入了相同的元素。在保证arr元素递增顺序的前提下,解决此重复的方法便是对DFS中的短枝进行剪枝,即在第二次及之后分配到该数值时跳过该分支,即在图中绿圈处进行判断,并跳过该分支。

代码如下:

# get all subset of arr without duplication

def dfs(arr, start, path, res):
    res.append(path)
    for i in range(start, len(arr)):
        if i > start and arr[i] == arr[i - 1]:  # IMPORTANT! avoid duplicate
            continue
        dfs(arr, i + 1, path + [arr[i]], res)

def get_subset_without_duplication(arr):
    arr.sort()  # ensure order
    res = []
    dfs(arr, 0, [], res)
    return res

arr = [1, 2, 2, 3]
get_subset_without_duplication(arr)

实际中此算法的应用:

leetcode第40题,给一个目标数和一个可能包含重复数字的列表,从列表中任选若干个数,使他们的和等于目标数,每个数仅可用一次。

解法参考:

# solve of leetcode problem 《40. Combination Sum II》
# https://leetcode.com/problems/combination-sum-ii/

def dfs(arr, target, start, path, res):
    if target == 0:
        res.append(path)
        return
    for i in range(start, len(arr)):
        if i > start and arr[i] == arr[i - 1]:  # IMPORTANT! avoid duplicate
            continue
        if arr[i] > target:
            break
        dfs(arr, target - arr[i], i + 1, path + [arr[i]], res)

def solve(arr, target):
    arr.sort()
    res = []
    dfs(arr, target, 0, [], res)
    return res

arr = [10,1,2,7,6,1,5]
target = 8
solve(arr, target)

本文中出现的代码在此可以找到:https://github.com/bunnyxt/lab/tree/master/dfs_subset

分类: DFS

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注