DEV Community

Dev Cookies
Dev Cookies

Posted on

Blog 2: Subset & Power Set Pattern

Backtracking is especially powerful for problems where we need to explore all possible subsets or combinations of elements. This is one of the most fundamental and reusable patterns in coding interviews.

🔹 Problem Definition

Given a set of elements, generate all subsets (the power set).

📌 Example:
Input: [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

🔹 Intuition

Each element has two choices:

  • Include it in the subset.
  • Exclude it from the subset.

👉 This forms a binary decision tree, leading to 2^n subsets for n elements.

🔹 Universal Template for Subsets 

void backtrack(int index, List<Integer> current, int[] nums, List<List<Integer>> results) {
    if (index == nums.length) {
        results.add(new ArrayList<>(current));
        return;
    }

    // 1. Exclude nums[index]
    backtrack(index + 1, current, nums, results);

    // 2. Include nums[index]
    current.add(nums[index]);
    backtrack(index + 1, current, nums, results);

    // Undo choice
    current.remove(current.size() - 1);
}
Enter fullscreen mode Exit fullscreen mode

🔹 Java Implementation – Power Set 

import java.util.*;

public class SubsetsPattern {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, results);
        return results;
    }

    private void backtrack(int index, List<Integer> current, int[] nums, List<List<Integer>> results) {
        if (index == nums.length) {
            results.add(new ArrayList<>(current));
            return;
        }

        // Exclude
        backtrack(index + 1, current, nums, results);

        // Include
        current.add(nums[index]);
        backtrack(index + 1, current, nums, results);

        // Backtrack (undo)
        current.remove(current.size() - 1);
    }
}
Enter fullscreen mode Exit fullscreen mode

🔹 Recursion Tree Visualization

For input [1,2]:

              []
         /           \
      []              [1]
     /   \           /   \
   []    [2]     [1]     [1,2]
Enter fullscreen mode Exit fullscreen mode

📌 Paths represent choices → Each leaf is a subset.

🔹 Variations in Interviews

  1. Subsets with Duplicates
  • Input: [1,2,2]
  • Avoid duplicate subsets.
  • Use sorting + skip duplicates. 
   private void backtrackDup(int start, List<Integer> current, int[] nums, List<List<Integer>> results) {
       results.add(new ArrayList<>(current));

       for (int i = start; i < nums.length; i++) {
           if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicate
           current.add(nums[i]);
           backtrackDup(i + 1, current, nums, results);
           current.remove(current.size() - 1);
       }
   }
Enter fullscreen mode Exit fullscreen mode
  1. Subsets of Size k
  • Input: nums=[1,2,3], k=2
  • Output: [ [1,2], [1,3], [2,3] ] 
   private void backtrackK(int start, int k, List<Integer> current, int[] nums, List<List<Integer>> results) {
       if (current.size() == k) {
           results.add(new ArrayList<>(current));
           return;
       }

       for (int i = start; i < nums.length; i++) {
           current.add(nums[i]);
           backtrackK(i + 1, k, current, nums, results);
           current.remove(current.size() - 1);
       }
   }
Enter fullscreen mode Exit fullscreen mode
  1. Subsets of a String
  • Input: "abc"
  • Output: ["", "a", "b", "c", "ab", "ac", "bc", "abc"]

(Same logic, just characters instead of integers.)

🔹 Complexity Analysis

  • Time Complexity: O(2^n) (all subsets).
  • Space Complexity: O(n) recursion depth + output storage.

🔹 Key Takeaways

✅ Subset problems always follow include/exclude pattern.
✅ Use sorting + skip duplicates for arrays with duplicates.
✅ For fixed-size subsets, add a size constraint check.
✅ This pattern is a building block for combinations, partitioning, and decision-making problems.

🔹 What’s Next?

In Blog 3: Permutation Pattern, we’ll see how backtracking generates all permutations of elements — another frequent interview favorite (with and without duplicates).

Top comments (0)