Skip to content

子集合问题

子集合问题

78. Subsets

子集合是全排列的好朋友,也是combination组合的好朋友，排列·组合·子集，他们三个都是好朋友.

从空开始加

同样先来看'ABC'

def recsubsets(sofar, rest):
    if rest == '':
        print sofar, 
    else:
        recsubsets(sofar, rest[1:])
        recsubsets(sofar + rest[0], rest[1:])

def listsubsets(s):
    recsubsets('',s)


listsubsets('ABC')
市面流行思路

市面上流行的思路：

  • [[],[1]] 是 [1] 的子集合
  • [[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2

所以用python写起来也很简单/精美

def subsets(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    results = [[]]
    for num in nums:
        results.extend([result + [num] for result in results])
    return results

我在这里犯过错，所以这一句

results.extend([result + [num] for result in results]) 实际上等于：

tmp = []
for result in results:
    tmp.append(result + [num])
results.extend(tmp)

http://stackoverflow.com/questions/38600315/python-power-set-cant-figure-out-my-error

90. Subsets II

要去重了,比如如果有 [1,2,2]，那么解答为：

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

现在来观察规律，与之前有不同之处是我们需要一个位置来mark，因为不再需要往之前出现过的地方再加了，看这个:

[[],[1]] 是 [1] 的子集合
[[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2
新来的2不能再从头开始加了，它需要从[ .., [2],[1,2] ]加 才是合理的

所以看到非常精妙的代码

def subsets(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    nums.sort()
    result = [[]]
    temp_size = 0

    for i in range(len(nums)):
        start = temp_size if i >= 1 and nums[i] == nums[i-1] else 0
        temp_size = len(result)
        #print start,temp_size,result
        for j in range(start, temp_size):
            result.append(result[j] + [nums[i]])
    print result

subsets([1,2,2])

这里这个start是来记录了之前一次数组的长度，temp_size记住目前数组的长度，然后用这个来达到去重的目的，非常聪明

回到顶部