算法_回溯_子集 II

文章目录

  • 子集 II
    • 1.解法
    • 2.总结

子集 II

leetcode链接

1.解法

这道题和我之前解的一道题比较类似(组合II)

首先想如果我们先不考虑集合中有重复元素的情况,那么这道题就成了一个简单的子集问题,而简单的子集问题之前我已经写过了,可以先看看(子集)

代码如下:

def subsets(nums):
    result = []
    path = []

    def backtracking(nums,startindex):
        path1 = path.copy() # 注意这里要写到出口前面,一是可以得到空集,二是可以得到本身
        result.append(path1)

		if startindex>=len(nums): # 其实这个出口可以不写,因为startindex>=len(nums)满足时,下面的for循环也要返回了。
			return

        for i in range(startindex,len(nums)):
            path.append(nums[i])
            backtracking(nums,i+1)
            path.pop()

    backtracking(nums,0)
    return result

现在我们考虑子集中含有重复元素的情况。先看一个例子[1,2,2],对于这个例子,如果我们用上面的代码来计算子集,会得到 [ [],[1],[2],[2],[1,2],[1,2],[2,2],[1,2,2] ]。

其中[2],[1,2]会重复,而导致这种重复是因为重复取了2,而我们如果每次只取一次2,那么就不会出现重复的问题了。那么怎么来实现这种操作呢?

首先我们可以先对集合从小到大排序,这样相同的元素就会凑在一起,这样的话,我们只要每次判断当前取得元素和上一次元素是否相同,如果相同,就不取了,如果不同,再取。换句话说,就是每次都只取凑在一起的相同元素的最后一个元素。

所以我们可以再循环中加一个判断条件,就是:

if i>startindex and nums[i]==nums[i-1]:
    continue

i>startindex:就是保证nums[i-1]不越界
nums[i]==nums[i-1]:就是保证在当前集合中,该数值和上一个数值重复了

如果都成立,那么就会导致重复,所以就不取了,直接continue即可。

最终代码如下:

def subsetsWithDup(nums):
    result = []
    path = []
    nums = sorted(nums)

    def backtracking(nums,startindex):
        path1 = path.copy()
        result.append(path1)

        for i in range(startindex,len(nums)):
            if i>startindex and nums[i]==nums[i-1]:
                continue

            path.append(nums[i])
            backtracking(nums,i+1)
            path.pop()

    backtracking(nums,0)
    return result

2.总结

集合去重的方法:

if i>startindex and nums[i]==nums[i-1]:
    continue

你可能感兴趣的