Search code examples
pythonrecursionsubsetbacktracking

finding all k subsets using recursion

I'm trying to find a way to make a recursive algorithm that will give all the k-length subsets of a set of numbers (0 -> n), but I cannot send a list to the function as an argument.

Eventually I want to return a list of lists

I thought on starting from the end, using some kind of DP. None of the things I've tried got even close to it

Thank you

Solution

  • Handling the last element (n-1) first allows you to not pass intermediate results with the given function signature:

    def subsets(n, k):
    if n < k or k < 0:
        return []
    if k == n:
        return [list(range(k))]
    return subsets(n-1, k) + [s+[n-1] for s in subsets(n-1, k-1)]

>>> subsets(3, 2)
[[0, 1], [0, 2], [1, 2]]
>>> subsets(4, 2)
[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]]
>>> subsets(4, 3)
[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]