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

Question

我正在解决这样一个面试问题:

Given an array of integers and sum, check whether any combination adds up to the sum.

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

即使这不是解决此问题的最佳方法，我也会遇到需要生成列表的所有组合或对其执行某些操作的问题，我想知道如何处理该问题。

Answer 1

一个方便的见解是认识到从 0 到 (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

这使得按设定顺序遍历所有可能的选择变得非常容易(这样就不可能跳过或重复访问任何潜在的选择)。