Recursion Part-2

Recap

This is another continuation of my previous blog on recursion.

So we have now learned that in a recursive function, the function will be calling itself inside init and there must be a/many base cases that can prevent calling this function based on the problem, in the previous blog we were able to solve the Climbing stair problem using recursion if you haven't seen it yet, I would highly recommend looking at it first before continuing this blog.

Another problem

Let's look at the below problem.

Combination

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints:

1 <= n <= 20

1 <= k <= n

I recommend you pause here, look at the problem, and think about the solution.

Solution:

Observations

return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.

Can you write the recurrence relation?

Well here is the Idea

At the given number n we have two choices
1. We can either include n in the combination or exclude it.
2. If we include n, then we decrease the k and if we don't then k will be the same.
3. If we include n in our combination then we have to find the next combination in the range [1, n-1]
  - it can be represented by combination(n-1, k-1)
4. If we don't include n then also we have to find the next combination in the range [1, n-1]
  - it can be represented by combination(n-1, k)

Here is the recurrence relation, we just discussed

$$Combination(n, k) = Combination(n-1, k-1) + Combination(n-1, k)$$

Now what would the base case(s) be?

think about a, remember the previous blog? think about the situation where we want to stop calculating the combinations in other words when the condition would be contradictory.
1. when k < 0 or n <0 it's an invalid case so stop/return here.
2. when k == 0; we don't want to go further, as from [1,n] numbers return combinations of 0 numbers, which means there is exactly one way we can do it, i.e. not selecting any numbers. so we stop here and push the result in our solution set.


    CombinationSet = set()
    def combination(n, k, currCombination = []):
        # base case(s)
        if k < 0 or n<0:
            return 
        if k == 0:
            CombinationSet.add(tuple(currCombination[:]))
            return 
        # include this number; 
        # meaning append it in the current combination set. 
        currCombination.append(n)
        # go and search next combination in [1, n-1]; decrease n and k by 1
        combination(n-1,k-1)
        # what if we don't want to include n
        # well then just pop the last number pushed 
        # from current combination
        currCombination.pop()
        # if we don't include this number then we just 
        # decrease n by 1 and keeping k same
        combination(n-1, k)

    combination(n, k)
    print(CombinationSet)