当我想检查一组的所有可能组合时,我会使用什么技术？

Question

我正在通过一个面试问题,如下所示:

给定一个整数和和的数组,检查是否有任何组合加起来.

当他们想要尝试一组的所有可能组合时,会使用什么编程技术？

即使这不是解决这个问题的最佳解决方案,我也会遇到需要生成或使用列表的所有组合执行某些操作的问题,并且我想知道如何处理它.

Answer 1

一个方便的见解是认识到来自0to 的所有数字的二进制表示(2^N)-1实际上是用于N不同项目中的可能组合的一组位掩码.例如,对于N=3(3项),因此(2^3)-1 = 7:

0: 000 = none
1: 001 = third item
2: 010 = second item
3: 011 = second and third items
4: 100 = first item
5: 101 = first and third items
6: 110 = first and second items
7: 111 = all 3 items

这使得以设定的顺序循环遍历所有可能的选择非常容易(因此不可能跳过或双重访问任何可能的选择).