Algorithms - lesson 4 | HackIndia Skills

Algorithms - lesson 4 | HackIndia Skills | HackIndia

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]

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

Recursion and backtracking

One idea

When to use it

Build the template

Subsets example

Copying too late

Explain complexity simply

README note

Do this now

Quick check