在python把一个set分成两个set

def num_splits(s, d):
    """找出到底有多少种方法把set s分成2段，前段的内的数值总和与后段内的数值总和的差距不大于d。

    >>> num_splits({1, 5, 4}, 0)  # splits to {1, 4} and {5}
    1
    >>> num_splits({6, 1, 3}, 1)  # no split possible
    0
    >>> num_splits({-2, 1, 3}, 2) # {-2, 3} {1} and {-2, 1, 3} {}
    2
    >>> num_splits({1, 4, 6, 8, 2, 9, 5}, 3)
    12

    
我们可以用以下方式把s分离出一个数值
    k = s.pop()
    rest = set(s)
    s.add(k)

 用以上方法分离后s不变，以及 {k}.union(rest) == s
    """

求大神解答，估计要用递归来写。。。

5 个解决方案

#1

大人，我没看懂

#2

set是关联容器，不是顺序容易，何必用set呢。

#3

将N元素的集合划分为2段 一共有 2^N种分法  
考虑到 分成的2个集合有重复的 比如 ｛1，2，3｝分成 ｛1｝，｛2，3｝和 ｛2， 3｝，｛1｝为同一种
故一共2^（N-1）种方法

可以将问题转化：

假设集合为 ｛a,b,c,d,e,f,g,h｝
0 0 0 0 0 0 0 1 
a b c d e f g h  => 表示划分为 ｛a,b,c,d,e,f,g｝｛h｝
如此以来 问题就简化为从1 -> 2^(N-1) 依次判断每个数字的2进制位是0 还是1 是1就累加  

还有集合的总和是知道的

#4

D = 5
S = [1,2,3, 4]

total = 0
for i in range(len(S)):
    total += S[i]

for x in range(2**len(S)):
    part1 = 0
    s1 = []
    s2 = []
    for i in range(len(S)):
        if (x>>i)%2 == 1:
            part1 += S[i]
            s1.append(S[i])
        else:
            s2.append(S[i])
    if abs(total - 2*part1) < D:
        print s1,s2

#5

D = 5
S = [1,2,3, 4]

for x in range(2**(len(S)-1)):
    part1 = 0
    part2 = 0
    s1 = []
    s2 = []
    for i in range(len(S)):
        if (x>>i)%2 == 1:
            part1 += S[i]
            s1.append(S[i])
        else:
            s2.append(S[i])
            part2 += S[i]
    if abs(part2 - part1) <= D:
        print s1,s2

改一下