Find all combinations of at least size k to n

Question

I'm struggling to figure out the formula for this problem:

Given an array of n numbers and a limit k, count all non-duplicate combinations that has at least size k.

E.g.: A=[1,2,3] k = 2 output = 4 // [1,2],[1,3],[1,2,3],[2,3]

The array can contain duplicate numbers.

E.g.: A=[1,1,2] k = 2 output = 3 // [1,1],[1,2],[1,1,2] but [1,2],[2,1], etc. are not accepted.

I was able to solve it using backtracking but TLE. I've been trying to find a formula from problems like find all combinations of n or find all combinations of size k without success.

I've figured out this table so far:

row = k
col = n
   1 2 3 4 5
  ---------
1| 1 2 3 4 5
2|   1 3 6 10
3|     1 4 10
4|       1 5

And the formula (not quite what I want) is:

combinations of size i with j numbers:
dp[i][j] = dp[i][j-1] + dp[i-1][j-1]

count(n,k) combinations of size k with n numbers
count(2,1) = 2
count(4,3) = count(3,3) + count(3,2) = 1 + 3 = 4
count(5,2) = count(4,2) + count(4,1) = 6 + 4 = 10
and so on

Update

Based on Oliver Dain's answer, here's the code if you're interested

def count_combinations(n, k):
    count = 0
    for i in range(k, n + 1):
        count += math.factorial(n)/(math.factorial(i)*math.factorial(n - i))
    return int(count)

Why isn't ```[2,3]``` included in the answer for ```A=[1,2,3]```? — Abhinav Mathur, Oct 29 '20 at 20:48
The array can contain duplicate entries. No, I can't do that. I'll update the question. — Viet, Oct 29 '20 at 20:50

score 3 · Accepted Answer · answered Oct 29 '20 at 20:53

3

First figure out how many unique values there are in the array (e.g. in most programming languages you could just throw them into a set and then find the size of that set). Let's say there's u unique values. Then you're answer is the sum of u choose p for all values of p between k and u (inclusive on both ends).

answered Oct 29 '20 at 20:53

Oliver Dain

9,617
3
35
48

Ahhh! Thank you for the link. That's super helpful! I've figured it out. – Viet Oct 29 '20 at 21:00
1

Glad that helps. By the way, note that factorials get big really fast so beware integer overflow. – Oliver Dain Oct 29 '20 at 21:13

Golden Lion · Answer 2 · 2021-02-01T12:45:16.987

0

use set to remove the duplicates

see for how set removes duplicates Remove duplicate tuples from a list if they are exactly the same including order of items

edited Feb 01 '21 at 12:45

answered Feb 01 '21 at 12:23

Golden Lion

3,840
2
26
35

what does size mean in the count? I didn't understand that part of the problem – Golden Lion Feb 01 '21 at 12:34

Find all combinations of at least size k to n

Update

2 Answers2