我用的是什么技术时，我想检查一组所有可能的组合？ [英] What technique do I use for when I want to check all possible combinations of a set?

问题描述

我通过面试问题的是这样的工作

  

鉴于整数和总和的阵列，   检查是否有结合加起来   到的总和。

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

即使不是这个问题的最佳解决方案，我碰到过的问题，我需要可生成或做一些与列表的所有组合，我想知道如何处理。

解决方案

一个方便的洞察力是实现所有数字的二进制再presentation从 0 来（2 ^ N）-1 实际上是一组位掩码的可能组合出 N 不同的项目。例如，对于 N = 3 （3项），从而（2 ^ 3）-1 = 7 ：

  0：000 =无
1：001 =第三个项目
2：010 =第二个项目
3：011 =第二项和第三项
4：100 =第一项
5：101 =第一项和第三项
6：110 =第一和第二项
7：111 =所有3个项目
 

这使得它很容易遍历所有可能的选项中设置的顺序（所以它不可能跳过或双访问任何潜在的选择）。

I'm working through an interview question that goes like:

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

What programming technique does one use when they want to try all possible combinations of a set?

Even if that isn't the best solution to this problem, I come across problems where I need to either generate or do something with all combinations of a list, and I'd like to know how to handle that.

解决方案

One handy insight is to realize that the binary representation of all numbers from 0 to (2^N)-1 is actually a set of bit masks for the possible combinations out of N distinct items. For instance, for N=3 (3 items) and thus (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

This makes it very easy to loop through all possible selections in a set order (so that it's impossible to skip or double-visit any potential selection).

这篇关于我用的是什么技术时，我想检查一组所有可能的组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！