获取列表所有子列表的快速方法

Question

我最近搞砸了一次编码面试，因为我无法足够快地生成列表中所有可能的子列表。更具体地说：（使用python）

• 我们得到了一个字符串编号列表["1", "3", "2", ...]
• 这个大小为6的列表中有多少子列表可以被16除
• 请注意，虽然原始列表中的元素可能不是唯一的，但在构建子列表时应将它们视为唯一的。例如，对于[1, 1, 1]，前两个1和后两个1的子列表是不同的子列表

使用itertools.combinations我能够足够快地生成我的所有子列表，但是在所有这些子列表中循环以确定哪些子列表可以被16“划分”太慢了

那么有没有办法以与itertools.combations相同的速度（或更快的速度）创建子列表，在创建每个子列表时检查它们是否可以被16整除

任何见解都将不胜感激

Answer 1

对列表进行排序。 找到最小的列表（按长度），其总和至少为16，并且可以被它整除（比如s）。 然后检查从s到6的所有尺寸列表。 这将以指数方式减少大小的数量，因为子列表的长度越大，子列表的数量就越少