Subset Product，子集的乘积

给定一个数字集合，给定一个值，判断是否可以用此数字集合的一个子集中的所有数字相乘，来得到这个给定的值。每个数字只能使用一次，重复的数字算多个数字。如果得到的子集内只有一个数字，相乘就是乘1。

Examples:

- given P = 10, and the list [2, 3, 4, 5], we see that 2*5 = 10, so the answer is yes
- given P = 81, and the list [2, 2, 3, 3, 4, 9], 3*3*9 = 81, so the answer is yes
- given P = 100 and the list [3, 4, 5, 8, 10], the answer is no

此题与找零问题对比，也是寻找一个满足条件的组合，不同点在于，子集中的每个元素，只能使用一次，除非给出多次！

def can_product(p: int, vals: tuple[int]) -> bool:
    if p == 1:
        return True
    while len(vals) and p%vals[-1]!=0:
        vals.pop()
    if not vals:
        return False
    if can_product(p//vals[-1], vals[:-1]):
        return True
    return can_product(p, vals[:-1])


assert can_product(2, (2)) == True
assert can_product(6, (2,3,4)) == True
assert can_product(9, (2,3,4)) == False
assert can_product(9, (3,3,3,3)) == True
assert can_product(12369, (3,4,5,8,19,20,31)) == False

思路：先排除掉无法除尽的除数，然后分情况，用某个数，不用某个数，不管用不用，这个数在后续递归中都不再出现。1对于乘法来说是个特殊值，应预先排除掉，不应作为输入！。

def can_product_d(p: int, vals: tuple[int]) -> list[tuple[int,...]]:
    if p == 1:
        return [()]
    while len(vals) and p%vals[-1]!=0:
        vals.pop()
    if not vals:
        return []
    i = [z+(vals[-1],) for z in can_product_d(p//vals[-1],vals[:-1])]
    j = can_product_d(p, vals[:-1])
    return i+j


assert len(can_product_d(2, (2)))   > 0
assert len(can_product_d(6, (2,3,4))) > 0
assert len(can_product_d(9, (2,3,4))) == 0
assert len(can_product_d(9, (3,3,3,3))) > 0
assert len(can_product_d(12369, (3,4,5,8,19,20,31))) == 0


from pprint import pprint
pprint(can_product_d(2, (2)))
pprint(can_product_d(16, (2,4,4,6,8,16)))
pprint(can_product_d(12369, (3,4,5,8,19,20,31)))

[(2,)]
[(16,), (2, 8), (4, 4)]
[]

对找零问题的深入分析，我们得到一个结论，就算是用DP的思路，有recursive时，算法都不太有实际价值，因为无法控制recursive的深度。（我理解AVLTree是一个可以控制recursive深度的数据结构）

def can_product_loop(p: int, vals: list[int]) -> bool:
    if p in vals:
        return True
    vlst = [v for v in vals if p%v==0]
    if (n:=len(vlst)) == 0:
        return False
    r1 = {v:[(v,)] for v in vlst}
    for i in range(n-1):
        r2 = {}
        for k,c in r1.items():
            for t in c:
                v = vlst[:]
                for e in t:
                    v.remove(e)
                for z in v:
                    q = k * z
                    if q == p:
                        return True
                    elif q < p:
                        r2.setdefault(q,[]).append(t+(z,))
        if not r2:
            return False
        r1 = r2
    return False

r2在r1的基础上构建，每一轮迭代后，r2变成新的r1。r1作为中间结果，它不是用来查询，而是在其基础上继续计算，正如和为N的加法算式。相同的q，list内可能有多个tuple，可能多个tuple是重复的，比如[(2,4),(4,2)]这样的重复，anyway，代码只要遇到一个相等，就直接return True，不做去重了。

我们继续折腾......现在尝试将乘积结果符合要求的所有组合找出来。

def can_product_loop_d(p: int, vals: list[int]) -> list[tuple[int]]:
    r = []
    if p in vals:
        r.append((p,))
    vlst = [v for v in vals if p%v==0 and p!=v]
    if (n:=len(vlst)) == 0:
        return r
    r1 = {v:[(v,)] for v in vlst}
    for i in range(n-1):
        r2 = {}
        for k,c in r1.items():
            for t in c:
                v = vlst[:]
                for e in t:
                    v.remove(e)
                for z in v:
                    q = k * z
                    if q == p:
                        a = tuple(sorted(t+(z,)))
                        if a not in r:
                            r.append(a)
                    elif q < p:
                        r2.setdefault(q,[]).append(t+(z,))
        if not r2:
            break
        r1 = r2
    return r

>>> can_product_loop_d(64,[2,3,4,5,6,7,8,16,24,32])
[(2, 32), (4, 16), (2, 4, 8)]
>>> can_product_loop_d(32,[2,3,4,5,6,7,8,16,24,32])
[(32,), (2, 16), (4, 8)]
>>> can_product_loop_d(16,[2,3,4,5,6,7,8,16,24,32])
[(16,), (2, 8)]
>>> can_product_loop_d(24,[2,3,4,5,6,7,8,16,24,32])
[(24,), (3, 8), (4, 6), (2, 3, 4)]
>>> can_product_loop_d(12369, (3,4,5,8,19,20,31))
[]
>>> can_product_loop_d(16, (2,4,4,6,8,16))
[(16,), (2, 8), (4, 4)]