Print Subsequences of given length "k" from an Array

Question

Getting Runtime error for this code :-

import numpy as np
   def combination(inp,n,k,ans):
      if len(ans)==k:
        print(*ans)
      else:
        if len(inp)>0:
          b=[]
          b=ans.append(inp[0])
          combination(inp[1:],n,k,b)
          combination(inp[1:],n,k,ans)
n=int(input())
a=list(map(int,input().split()))
a=np.array(a)
k=int(input())
ans=[]
combination(a,n,k,ans)

But why it is showing run Time error for this ?

Answer 1

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments, and other side effects.

We can write fixed-length combinations choosek using inductive reasoning -

1. if size k is zero, yield the empty combination
2. (inductive) k is greater than zero. if the iterable it is empty, stop iteration
3. (inductive) k is greater than zero and the iterable it has at least one element. for each comb of the sub-problem choosek(it[1:], k - 1), prepend the first element of it to the resulting comb and yield each result of the sub-problem choosek(it[1:], k)

def choosek(it, k):
  if k == 0:
    yield ()                               #1
  elif not it:
    return                                 #2
  else:
    for comb in choosek(it[1:], k - 1):    #3
      yield (it[0], *comb)
    yield from choosek(it[1:], k)

Notice the print side effect is moved outside of the function so the caller can do whatever they choose with the resulting combinations -

for comb in choosek("", 2):
  print("".join(comb))