Recursive Function That Returns Combinations Of Size N Chosen From List

I am trying to write a recursive function which takes as its inputs an integer n, and a list l, and returns a list of all the combinations of size n that can be chosen from the ele

Solution 1:

First I would recommend that you layout your function like:

defget_combinations(array, n):
    solutions = []

    # all the code goes herereturn solutions

That way if there's a case that's a problem, like n == 0, you can just ignore it and get a valid (empty) result. The next issue is this line is wrong:

elif n == 1:
    return [array[0]]

The correct thing to do if n == 1 is to return an array with every element of the array wrapped in a list:

ifn== 1:
    solutions = [[element] for element in array]

This is your base case as the next layer up in the recursion will build on this. What comes next is the heart of the problem. If n > 1 and the array has content, then we need to loop over the indexes of the array. For each we'll call ourself recursively on everything past the current index and n - 1:

sub_solutions = get_combinations(array[index + 1:], n - 1)

This returns partial solutions. We need to stuff the element at the current index, ie. array[index], onto the front of each sub_solution in sub_solutions, and add each augmented sub_solution to our list of solutions that we return at the end of the function:

solutions.append([array[index]] + sub_solution)

And that's it!