如何计算组合（回溯）

本文总结多个计算组合问题的思路，最后介绍回溯算法的思路。

假设有一个集合A，内有元素N个，不管元素是否有相同的，问题是：找出所有的size=M的组合？（\(M<=N\)）

def factorial(n):
    r = 1
    for i in range(2,n+1):
        r *= i
    return r

f = factorial
assert f(4) == 24
assert f(5) == 24*5
assert f(6) == 24*5*6
assert f(7) == 24*5*6*7

a = tuple('123456abcdefghijklmn123456')
N = len(a)

s2 = [(a[i],a[j]) for i in range(N)
                  for j in range(i+1,N)]
assert len(s2) == f(N)/(f(N-2)*f(2))

s3 = [(a[i],a[j],a[k]) for i in range(N)
                       for j in range(i+1,N)
                       for k in range(j+1,N)]
assert len(s3) == f(N)/(f(N-3)*f(3))

s4 = [(a[i],a[j],a[k],a[m])
                for i in range(N)
                for j in range(i+1,N)
                for k in range(j+1,N)
                for m in range(k+1,N)]
assert len(s4) == f(N)/(f(N-4)*f(4))

寻找M个元素的组合，就是M重循环。上面代码assert语句内，有个计算组合数的公式，具体请参考：阶乘，排列和组合。

如果要得到没有重复元素的确定个数的组合，可以再做进一步处理，做个去重：

s4b = [t for t in s4 if len(set(t))==4]
print(len(s4))   # 14950
print(len(s4b))  # 13309

以上只是单纯的计算所有组合，并没有带任何过滤条件。有过滤情况的示例，如确定k的kSum（k数和）问题（2数和，3数和），寻找确定size组合的问题，在一个list中，寻找k个数出来，其和满足target。当存在过滤条件时，我们常常更够找到一些技巧，降低循环嵌套的深度，加快计算。

组合size不确定

允许重复元素

假设有一个集合A，内有元素N个，不管元素是否有相同的，问题是：找出集合A的所有子集。（既然集合A中存在可能存在重复元素，子集也允许重复元素，但在每个子集中，每个元素只能取一次）

先计算单个元素的组合，然后2个元素的组合，......，用M-1个元素的组合，计算M个元素的组合，直到最后的N个元素的组合：

def get_subset_dup(lst: list[int]) -> list[tuple[int]]:
    r = r1 = [(v,) for v in set(lst)]
    for i in range(len(lst)-1):
        r2 = []
        for s in r1:
            v = lst[:]
            for t in s:
                v.remove(t)
            for t in v:
                a = tuple(sorted(s+(t,)))
                if a not in r:
                    r.append(a)
                    r2.append(a)
        if not r2:
            break
        r1 = r2
    return r


print(get_subset_dup([1,2,3]))
print(get_subset_dup([1,2,3,3]))
print(get_subset_dup([1,2,2,2]))

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (3, 3), (1, 2, 3), (1, 3, 3), (2, 3, 3), (1, 2, 3, 3)]
[(1,), (2,), (1, 2), (2, 2), (1, 2, 2), (2, 2, 2), (1, 2, 2, 2)]

不允许重复元素

def get_subset(lst: list[int]) -> list[tuple[int]]:
    r = r1 = [(v,) for v in set(lst)]
    for i in range(len(lst)-1):
        r2 = []
        for s in r1:
            v = [t for t in lst if t not in s]
            for t in v:
                a = tuple(sorted(s+(t,)))
                if a not in r:
                    r.append(a)
                    r2.append(a)
        if not r2:
            break
        r1 = r2
    return r


print(get_subset([]))
print(get_subset([1]))
print(get_subset([1,2]))
print(get_subset([1,2,3]))
print(get_subset([1,2,3,4]))
print(get_subset([1,2,3,3]))
print(get_subset([1,2,2,2]))

[]
[(1,)]
[(1,), (2,), (1, 2)]
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
[(1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
[(1,), (2,), (1, 2)]

def get_subset(lst: list[int]) -> list[tuple[int]]:
    lstset = set(lst)
    r = [set((v,)) for v in lstset]
    for i in range(len(lstset)-1):
        for s in r[:]:
            v = lstset - s
            r += [s|{t} for t in v if s|{t} not in r]
    return r

示例问题

空间复杂度

如果集合A的size比100还要大，这似乎很容易，100并不是一个很大的数。那么，可以想想，计算出来的组合数，或者计算过程中需要保存的中间结果，数量非常庞大。这会成为一个问题！

回溯（backtrack）

回溯，backtrack，是另一个思路。我的理解是：回溯将循环拆解为递归，避免保存中间结果。

不确定size子集（回溯）

前文使用的算法，在计算不确定size的问题时，空间复杂度太高。而使用回溯算法，几乎不需要任何额外空间。

def comb(lst: list[int], a: list[int]):
    yield a
    for i in range(len(lst)):
        a.append(lst[i])
        yield from comb(lst[i+1:], a)
        a.pop()


data = [1,2,3,4]
for it in comb(data,[]):
    print(it)

[]
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[3]
[3, 4]
[4]