Python的itertools的空间复杂度

Question

我尝试编写一个子集和求解器，但具有更好的空间复杂性。

我的想法是，如果语句sum(jj) != target返回true。它删除了组合，从而节省了内存，但是我的印象是for循环必须记住所有组合，直到找到目标和为止。

或者，python已经在做我想做的事情。

所以这就是我得到的

import itertools
from itertools import combinations 


s=[2,3,4,6,7]

target = 5


for j in range(0, len(s)):
  for jj in combinations(s, j):
   if sum(jj) != target: 
     del(jj)
   else:
     print('yes', jj)
     quit()

输出

yes (2, 3)

Python是否可以与我的想法配合使用，而不是记住“返回”负子集和的所有其他组合？

Answer 1

什么使您想到for将“记住”某些内容？唯一的环境存储是循环索引jj。您的方法有益于空间复杂性：每次迭代仅考虑一种组合。 combinations是generator：在您需要时提供下一个组合only；在此之前，它仅保持其状态并等待您的调用。

del(jj)很危险：在循环处于活动状态时删除循环索引？从程序中删除该分支；只需处理积极的情况，并在必要时继续：

if sum(jj) == target:
    print(jj)
    break