CODEWITHSUNDEEP
algorithmtheory
zeh
zeh

Reputation: 10689

Finding number of combinations possible

I have a problem that is baffling me. I think there's an elegant solution, but I haven't been able to find it yet. The problem is as such:

I have a set of unique items. I am allowed to pick a maximum of n items from this set, to form a sub-set. The question then is, how many unique sub-sets are possible?

Say I have this set of 3 items:

A B C

And I am allowed to pick a maximum of 2 items from the set. The answers would be:

(none)
A
B
C
AB
AC
BC

That is, the answer is 7. There are 7 unique sub sets possible.

How do I get to that solution pro grammatically?

If it matters, my sets have up to 8 items, and the maximum number of items on my answers is up to 3. They vary, though, hence why I wanted to see if there's an easier, more elegant way to get to this without brute force counting.

Upvotes: 0

Views: 77

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65508

If you want the number of ways to choose at most k items from n, then you can sum the binomial coefficients n choose i for i from 0 to k, e.g.,

static int ways(int n, int k) {
  int sum = 0, nci = 1, i;
  for (i = 0; i <= k; i++) {
    sum += nci;
    nci *= n - i;
    nci /= i + 1;
  }
  return sum;
}

Upvotes: 3

Related Questions