Algorithms - lesson 4 | HackIndia Skills

Key point

One idea

Recursion solves a problem by calling the same function on a smaller problem. Backtracking is recursion where you try a choice, explore it, then undo it before trying the next choice.

When to use it

Use recursion when the problem naturally breaks into smaller copies. Common placement examples are subsets, permutations, combination sum, N-Queens, maze paths, and tree traversal.

The shape is usually: stop at a base case, loop over choices, make one choice, recurse, then undo the choice.

Your to-do

Build the template

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Define what your recursive function means in one sentence.
Write the base case first, including what you return or save.
List the choices available at the current step.
Make one choice and move to the smaller problem.
Undo the choice if you changed shared state.
Check the time complexity from the recursion tree.

0 of 6 done

Example

Subsets example

This is a clean first backtracking problem. For each number, you either include it or skip it.

Create a file like recursion_backtracking/subsets.py and add this code.

def subsets(nums):
    ans = []
    path = []

    def backtrack(i):
        if i == len(nums):
            ans.append(path.copy())
            return

        # choice 1: include nums[i]
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()  # undo

        # choice 2: skip nums[i]
        backtrack(i + 1)

    backtrack(0)
    return ans

if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # Expected: 8 subsets, including [] and [1, 2, 3]

Common mistake

Copying too late

A common bug is appending path directly to ans. That stores the same list reference many times, so later pop calls change saved answers too.

Use path.copy() when saving a current answer. Use path.pop() right after the recursive call that used path.append().

Tip

Explain complexity simply

For subsets, each item has two choices: include or skip. That gives 2^n leaves, and each saved subset can take up to n to copy.

So you can write: Time O(n * 2^n), space O(n) recursion depth, excluding output storage. This is enough for a README explanation.

Example

README note

Add a short note near this problem in your repo README. Recruiters should see your thinking, not only code.

### Recursion and backtracking: Subsets

Problem: Generate all subsets of a list of distinct integers.

Approach:
I use backtracking. At each index, I make two choices: include the number or skip it. When I reach the end, I save a copy of the current path.

Base case:
When index == len(nums), save path.copy().

Complexity:
Time: O(n * 2^n), because there are 2^n subsets and copying each subset can take O(n).
Space: O(n) recursion depth, excluding the output list.

Sample run:
Input: [1, 2, 3]
Output count: 8