The Subsets Pattern is widely used in combinatorial problems where we need to explore all combinations, subsets, or decisions (take/not take).
Amazon often uses this to test recursion + backtracking + BFS/DFS skills.

🔑 When to Use Subsets Pattern?

  • Generate all subsets / combinations of a set
  • Handle decision-based recursion (pick or not pick)
  • Solve problems with combinatorial explosion (powerset, permutations, combination sums)
  • Explore feature toggles / inclusion-exclusion

📝 Problem 1: Generate All Subsets

👉 Amazon-style phrasing:
Given a set of distinct integers nums, return all possible subsets (the power set).

Java Solution (Backtracking) 

import java.util.*;

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

    private static void backtrack(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current)); // add current subset

        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);             // include nums[i]
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1); // backtrack
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(subsets(nums));
    }
}

✅ Time Complexity: O(2^n)
✅ Space Complexity: O(n) recursion depth

📝 Problem 2: Subsets With Duplicates

👉 Amazon-style phrasing:
Given a collection of integers nums that might contain duplicates, return all possible subsets without duplicates.

Java Solution 

public class SubsetsWithDup {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // sort to handle duplicates
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) continue; // skip duplicates
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

✅ Amazon Insight:
Tests your ability to handle duplicates gracefully with sorting + skipping.

📝 Problem 3: Letter Case Permutation

👉 Amazon-style phrasing:
Given a string s, return all possible strings after toggling case of each letter.

Java Solution 

public class LetterCasePermutation {
    public static List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s.toCharArray(), 0, new StringBuilder(), result);
        return result;
    }

    private static void backtrack(char[] chars, int index, StringBuilder current, List<String> result) {
        if (index == chars.length) {
            result.add(current.toString());
            return;
        }

        char c = chars[index];
        if (Character.isLetter(c)) {
            current.append(Character.toLowerCase(c));
            backtrack(chars, index + 1, current, result);
            current.deleteCharAt(current.length() - 1);

            current.append(Character.toUpperCase(c));
            backtrack(chars, index + 1, current, result);
            current.deleteCharAt(current.length() - 1);
        } else {
            current.append(c);
            backtrack(chars, index + 1, current, result);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

✅ Amazon Insight:
Tests creativity — it’s still a subsets problem but disguised with characters instead of numbers.

📝 Problem 4: Generate Balanced Parentheses

👉 Amazon-style phrasing:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Java Solution 

public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private static void backtrack(List<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }

        if (open < max) backtrack(result, current + "(", open + 1, close, max);
        if (close < open) backtrack(result, current + ")", open, close + 1, max);
    }
}

✅ Amazon Insight:
Tests recursion depth + constraints (open ≤ close).

📚 Extended Problem List (Amazon Patterns)

  1. Combination Sum (LeetCode 39)
  2. Combination Sum II (LeetCode 40) – with duplicates
  3. Permutations (LeetCode 46)
  4. Permutations II (LeetCode 47) – with duplicates
  5. Word Search II (Backtracking in Grid)
  6. Sudoku Solver (Hard Backtracking)

🎯 Key Takeaways

  • Subsets pattern = decision making (take / skip).
  • Natural recursion fits these problems well.
  • Amazon loves duplicates handling (sorting + skipping).
  • Expect parentheses, toggling, or string variants.

📅 Next in the series (Day 11):
👉 Modified Binary Search Pattern – super popular in Amazon interviews for rotated arrays, searching in infinite arrays, and tricky conditions.