Print all subsequences/Power Set: Complete Guide with Backtracking

Hey students! If you’re diving into recursion and backtracking, the “Subsets” problem (also known as generating the power set or all subsequences) is a perfect starting point. It’s like deciding what to pack for a trip, for each item, you choose to take it or leave it, and all combinations are possible.

Here’s the [Problem Link] to begin with.

Today, we’ll focus on solving it using backtracking, a technique that’s super useful for exploring all possibilities. I’ll explain it in simple terms, step by step, so even beginners can follow along. Let’s get started!

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Solution: Backtracking Approach

Intuition

Backtracking is like exploring a maze where you try different paths, and if you hit a dead end, you go back (backtrack) and try another way. For subsets, think of it as making choices for each element in the array: “Do I include this number in my current subset or not?” We start from the first element, make a choice to include it (add it to our subset and move to the next), then backtrack by removing it and trying the “exclude” choice. This builds a tree of decisions, and each complete path gives us one subset. It’s perfect for generating all combinations without duplicates!

Detailed Approach

1. Recursive Function: We create a helper function solve that takes the current index in the array, the current subset being built, the original array, and the result list.
2. Base Case: If the index reaches the end of the array (we’ve made choices for all elements), add a copy of the current subset to the result.
3. Include Choice: Add the current element to the subset, then recurse to the next index.
4. Backtrack: After exploring the “include” path, remove the last element (pop it) to undo the choice.
5. Exclude Choice: Recurse to the next index without adding the current element.
6. Start Recursion: Call the function with index 0 and an empty subset.
7. Return Result: The result list will contain all subsets.

This way, we systematically explore all 2^n possibilities (for n elements).

Code

from typing import List

class Solution:
    def solve(self, index: int, subset: List[int], nums: List[int], result: List[List[int]]):
        # Base case: We've processed all elements, add current subset to result
        if index >= len(nums):
            result.append(subset.copy())  # Use copy to avoid modifying later
            return
        
        # Choice 1: Include the current element in the subset
        subset.append(nums[index])    # Add to current subset
        self.solve(index + 1, subset, nums, result)  # Recurse to next index
        
        # Backtrack: Undo the inclusion to try the exclude choice
        subset.pop()                  # Remove the last added element
        
        # Choice 2: Exclude the current element
        self.solve(index + 1, subset, nums, result)  # Recurse without adding

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []                   # List to store all subsets
        self.solve(0, [], nums, result)  # Start from index 0 with empty subset
        return result

Code Explanation

The solve function is our backtracking hero. It starts at index 0 with an empty subset. For each element, it first tries including it (append to subset, recurse), then backtracks (pop) and tries excluding it (just recurse without appending). When it reaches the end (index == len(nums)), it means we’ve made choices for every element, so we add a copy of the subset to the result. The copy is important because subsets are lists, and we don’t want future changes to affect already added ones. This builds all subsets by exploring the decision tree.

Time and Space Complexity

• Time Complexity: O(n * 2^n) – We explore 2^n subsets (each element has 2 choices), and copying each subset takes O(n) time in the worst case.
• Space Complexity: O(n) – The recursion stack can go up to depth n, plus space for the current subset. (Result space is separate, as it’s the output.)

Simplifying It

Backtracking is like playing a choose-your-own-adventure game. At each step (element), you have two adventures: “include me” or “skip me.” You try one, see where it leads (recurse), then come back (backtrack) and try the other. When you finish the book (reach the end of the array), you note down the story (add the subset). It’s a systematic way to try all possibilities without missing any or creating duplicates. Perfect for problems like subsets, permutations, or combinations!

This backtracking approach is elegant and helps build intuition for more complex problems. Practice it by drawing the recursion tree for small inputs, it’ll click fast! If you have questions or need more examples, let me know. Happy coding! 🚀

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.