📚 Subsets Pattern – Java Cheat Sheet

📌 What Is It?

The Subsets Pattern is used to generate all possible subsets (or combinations) of a given set. This pattern is commonly used in problems involving combinations, permutations, and subsets.

🧱 Pattern Templates

1️⃣ Recursive Approach

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

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

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

2️⃣ Iterative Approach

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // Start with the empty subset

        for (int num : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> newSubset = new ArrayList<>(result.get(i));
                newSubset.add(num);
                result.add(newSubset);
            }
        }

        return result;
    }
}

3️⃣ Bitwise Approach

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int totalSubsets = 1 << n; // 2^n subsets

        for (int subsetMask = 0; subsetMask < totalSubsets; subsetMask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((subsetMask & (1 << i)) != 0) { // Check if the i-th bit is set
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }

        return result;
    }
}

4️⃣ Subsets with Duplicates

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

    private void generateSubsets(int index, int[] nums, 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]);
            generateSubsets(i + 1, nums, current, result);
            current.remove(current.size() - 1); // Backtrack
        }
    }
}

5️⃣ Permutations

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }

    private void generatePermutations(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(nums[i]);
            generatePermutations(nums, used, current, result);
            current.remove(current.size() - 1); // Backtrack
            used[i] = false;
        }
    }
}

6️⃣ Combinations

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        generateCombinations(1, n, k, new ArrayList<>(), result);
        return result;
    }

    private void generateCombinations(int start, int n, int k, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i <= n; i++) {
            current.add(i);
            generateCombinations(i + 1, n, k, current, result);
            current.remove(current.size() - 1); // Backtrack
        }
    }
}

📊 Time Complexity

Subsets: O(2^N), where N is the size of the input array.
Permutations: O(N!), where N is the size of the input array.
Combinations: O(C(N, K)), where C(N, K) is the number of combinations.

✅ Use Cases

Generating all subsets of a set
Finding combinations or permutations
Solving problems involving power sets

📘 Common LeetCode Problems

78. Subsets [Medium] Backtracking 📄 Cheat Sheet
90. Subsets II [Medium] Backtracking 📄 Cheat Sheet
46. Permutations [Medium] Backtracking 📄 Cheat Sheet
77. Combinations [Medium] Backtracking 📄 Cheat Sheet
17. Letter Combinations of a Phone Number [Medium] Backtracking 📄 Cheat Sheet
22. Generate Parentheses [Medium] Backtracking 📄 Cheat Sheet
784. Letter Case Permutation [Easy] Backtracking 📄 Cheat Sheet
1079. Letter Tile Possibilities [Medium] Backtracking 📄 Cheat Sheet

🧪 Example: Subsets

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

Explanation:
- The subsets of [1,2,3] are generated using backtracking.

💡 Pro Tips

Use backtracking to explore all possible subsets efficiently.
For problems with duplicates, sort the input and skip duplicate elements during recursion.
Edge cases: empty input, single-element input.