Recursion - Print unique subsets And Variations

📋 Table of Contents

1. Core Concepts

2. Problem Variations

3. Approach & Algorithm

4. Recursion Tree Analysis

5. Implementation

6. Advanced Variations

7. Key Takeaways

🎯 Core Concepts

What are we solving?

Three different names for the SAME problem:

• Print all Subsets

• Print all Subsequences

• Print Power Set

Key Definitions

1. Subsequence

Input: "abc"
Subsequences: "", "a", "b", "c", "ab", "ac", "bc", "abc"

• Order matters - elements must maintain their relative order

• Can skip elements but cannot rearrange

• If 'a' comes before 'b' in input, 'a' must come before 'b' in subsequence

2. Subset

Input: {a, b, c}
Subsets: {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

• Order doesn't matter - {a,b} same as {b,a}

• Just a collection of elements

3. Power Set

Set: {a, b, c}
Power Set: {{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

• Set of all possible subsets

• If set has n elements, power set has 2^n elements

🔄 Problem Variations

Common Question Formats:

1. Print all Subsets

2. Print all Subsequences

3. Print Power Set

4. Print unique Subsets (when duplicates exist)

5. Print in Lexicographical order

Important: All these are essentially the same problem with minor variations!

🚀 Approach & Algorithm

The "Take or Not Take" Method

For each element, we have 2 choices:

1. Take the element (include in current subset)

2. Don't take the element (exclude from current subset)

Basic Algorithm Structure:

public static void generateSubsets(int index, List<Integer> currentSubset, int[] inputArray) {
    if (index == inputArray.length) {
        System.out.println(currentSubset);
        return;
    }
    
    // Choice 1: Don't take current element
    generateSubsets(index + 1, currentSubset, inputArray);
    
    // Choice 2: Take current element
    currentSubset.add(inputArray[index]);
    generateSubsets(index + 1, currentSubset, inputArray);
    currentSubset.remove(currentSubset.size() - 1);  // backtrack
}

🌳 Recursion Tree Analysis

Example: Input = "abc"

                    f(0, "")
                   /        \
              (don't take 'a')  (take 'a')
                 /                    \
            f(1, "")                f(1, "a")
           /        \              /        \
    (don't take 'b') (take 'b')  (don't take 'b') (take 'b')
       /              \            /              \
   f(2, "")        f(2, "b")   f(2, "a")      f(2, "ab")
   /      \        /      \     /      \       /      \
(don't)  (take)  (don't) (take) (don't) (take) (don't) (take)
  |       |       |       |      |       |      |       |
f(3,"")  f(3,"c") f(3,"b") f(3,"bc") f(3,"a") f(3,"ac") f(3,"ab") f(3,"abc")
  |       |       |       |      |       |      |       |
 ""      "c"     "b"     "bc"   "a"     "ac"   "ab"    "abc"

Tree Properties:

• Height: n (where n = length of input)

• Nodes: 2^n leaf nodes (each represents a subset)

• Time Complexity: O(2^n × n) - 2^n subsets, each taking O(n) to copy

• Space Complexity: O(n) - recursion depth

💻 Implementation

Method 1: Using ArrayList

import java.util.*;

public class SubsetGenerator {
    
    public static void printSubsets(int index, List<Integer> current, int[] arr) {
        // Base case
        if (index == arr.length) {
            // Print current subset
            System.out.print("[");
            for (int i = 0; i < current.size(); i++) {
                System.out.print(current.get(i));
                if (i < current.size() - 1) System.out.print(", ");
            }
            System.out.println("]");
            return;
        }
        
        // Don't take current element
        printSubsets(index + 1, current, arr);
        
        // Take current element
        current.add(arr[index]);
        printSubsets(index + 1, current, arr);
        current.remove(current.size() - 1); // backtrack
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        List<Integer> current = new ArrayList<>();
        printSubsets(0, current, arr);
    }
}

Method 2: Using String (for characters)

public class SubsequenceGenerator {
    
    public static void printSubsequences(int index, String current, String input) {
        if (index == input.length()) {
            System.out.println("'" + current + "'");
            return;
        }
        
        // Don't take
        printSubsequences(index + 1, current, input);
        
        // Take
        printSubsequences(index + 1, current + input.charAt(index), input);
    }
    
    public static void main(String[] args) {
        String input = "abc";
        printSubsequences(0, "", input);
    }
}

🔧 Advanced Variations

1. Unique Subsets (Handle Duplicates)

import java.util.*;

public class UniqueSubsets {
    
    public static void uniqueSubsets(int index, List<Integer> current, int[] arr, Set<List<Integer>> result) {
        if (index == arr.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Don't take
        uniqueSubsets(index + 1, current, arr, result);
        
        // Take
        current.add(arr[index]);
        uniqueSubsets(index + 1, current, arr, result);
        current.remove(current.size() - 1);
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 2};
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> current = new ArrayList<>();
        uniqueSubsets(0, current, arr, result);
        
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

2. Lexicographical Order

public class LexicographicalSubsets {
    
    public static void lexicographicalSubsets(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        
        generateSubsets(0, current, arr, result);
        
        // Result will be in lexicographical order
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
    
    private static void generateSubsets(int index, List<Integer> current, int[] arr, List<List<Integer>> result) {
        if (index == arr.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Don't take
        generateSubsets(index + 1, current, arr, result);
        
        // Take
        current.add(arr[index]);
        generateSubsets(index + 1, current, arr, result);
        current.remove(current.size() - 1);
    }
}

3. Using Map for Duplicates

import java.util.*;

public class MapBasedDuplicateHandler {
    
    public static void handleDuplicates(int[] arr) {
        Map<List<Integer>, Boolean> uniqueSubsets = new HashMap<>();
        List<List<Integer>> allSubsets = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        
        generateAllSubsets(0, current, arr, allSubsets);
        
        // Filter unique subsets using map
        for (List<Integer> subset : allSubsets) {
            if (!uniqueSubsets.containsKey(subset)) {
                uniqueSubsets.put(subset, true);
                System.out.println(subset);
            }
        }
    }
    
    private static void generateAllSubsets(int index, List<Integer> current, int[] arr, List<List<Integer>> allSubsets) {
        if (index == arr.length) {
            allSubsets.add(new ArrayList<>(current));
            return;
        }
        
        // Don't take
        generateAllSubsets(index + 1, current, arr, allSubsets);
        
        // Take
        current.add(arr[index]);
        generateAllSubsets(index + 1, current, arr, allSubsets);
        current.remove(current.size() - 1);
    }
}

📊 Complexity Analysis

Examples:

• Input length 3 → 2³ = 8 subsets

• Input length 4 → 2⁴ = 16 subsets

• Input length n → 2ⁿ subsets

🎓 Key Takeaways

Important Points:

1. Subset = Subsequence = Power Set (same problem, different names)

2. "Take or Not Take" is the core approach

3. Recursion tree has exactly 2^n leaf nodes

4. Backtracking is essential for space optimization

5. Order matters in subsequences, doesn't matter in subsets

Problem Recognition:

When you see these keywords → Use "Take or Not Take" recursion:

• Generate all subsets

• Print all subsequences

• Find power set

• All possible combinations

• Include/exclude elements

Common Mistakes to Avoid:

• Forgetting to backtrack (will give wrong results)

• Not handling duplicates properly

• Confusing subsets with subsequences

• Not considering empty subset

🔗 Related Problems

• Combination Sum

• Palindrome Partitioning

• Word Break

• Generate Parentheses

• Letter Combinations

Pro Tip: Master this "Take or Not Take" pattern - it's the foundation for many advanced recursion and backtracking problems!

Java-Specific Updates:

Data Structures:

• vector<int> → List<Integer> / ArrayList<Integer>

• set<vector<int>> → Set<List<Integer>> / HashSet<List<Integer>>

• map<vector<int>, bool> → Map<List<Integer>, Boolean> / HashMap<List<Integer>, Boolean>

Syntax Changes:

• arr.size() → arr.length

• push_back() → add()

• pop_back() → remove(current.size() - 1)

• cout → System.out.println()

• #include → import java.util.*

Java Best Practices:

• Added proper class structures with public static methods

• Used ArrayList for dynamic arrays

• Used Arrays.sort() for sorting

• Proper main method implementations

• Created new ArrayList instances when adding to collections to avoid reference issues

Key Java Features Highlighted:

• Collections Framework: ArrayList, HashSet, HashMap

• Generics: List<Integer>, Set<List<Integer>>

• Boxing/Unboxing: int ↔ Integer

• String manipulation: charAt(), string concatenation

Thirdmaster account 😀

To solve the problem without using the character logic inside the recursion (i.e., without tracking each character individually), and by storing the subsets directly into a map while checking for duplicates at the base case, we can approach it in the following way:

Approach:

1. Recursive Subset Generation:

The recursive function generates all subsets of the string by exploring the options of including or excluding the current character.

The base condition checks if the input string is empty, and if so, it adds the current subset to a Map.

2. Handling Duplicates:

The key idea is to use a Map<String, Integer> to store subsets. If a subset has already been generated (present in the map), we simply increment its counter. This avoids storing duplicates.

3. Lexicographical Order:

Instead of sorting the string at the start, we will use the map to ensure subsets are stored only once. However, for output to be in lexicographical order, we can simply iterate over the map's keys in sorted order when printing the subsets.

Java Code:

import java.util.*;

public class UniqueSubsetsWithMap {

public static void main(String[] args) {
    String input = "aab"; // Example input string
    Map<String, Integer> subsetMap = new HashMap<>(); // Map to store subsets and their counts

    // Start the recursion to generate subsets
    generateSubsets(input, "", subsetMap);
    
    // Sort the map keys to print subsets in lexicographical order
    List<String> sortedSubsets = new ArrayList<>(subsetMap.keySet());
    Collections.sort(sortedSubsets);
    
    // Print the subsets in lexicographical order
    for (String subset : sortedSubsets) {
        System.out.println(subset);
    }
}

// Recursive function to generate subsets
private static void generateSubsets(String input, String currentSubset, Map<String, Integer> subsetMap) {
    // Base case: if the input string is empty, add the current subset to the map
    if (input.isEmpty()) {
        subsetMap.put(currentSubset, subsetMap.getOrDefault(currentSubset, 0) + 1);
        return;
    }

    // Recursive case: Exclude the first character and recurse
    generateSubsets(input.substring(1), currentSubset, subsetMap);

    // Recursive case: Include the first character and recurse
    generateSubsets(input.substring(1), currentSubset + input.charAt(0), subsetMap);
}

}

Explanation:

1. Recursion:

The generateSubsets function is the recursive function that explores all subsets of the input string. It operates by either including or excluding the first character of the string in the current subset.

2. Base Case:

The base case occurs when the input string is empty. At this point, the currentSubset (which holds the current combination of characters) is added to the map with its count. The map ensures that duplicate subsets are counted, but only one instance of each unique subset is stored.

3. Map for Uniqueness:

We use a Map<String, Integer> to store subsets and their counts. The key is the subset itself, and the value is the count of how many times this subset has been generated. This prevents duplicate subsets from being stored, as we increment the count of the existing subset in the map if it is generated again.

4. Printing in Lexicographical Order:

After all subsets have been generated, we retrieve all the unique subsets from the map, sort them lexicographically using Collections.sort(), and then print them.

Example Walkthrough for input "aab":

Recursion unfolds like this:

generateSubsets("aab", "", subsetMap)
-> generateSubsets("ab", "", subsetMap)
-> generateSubsets("b", "", subsetMap)
-> generateSubsets("", "", subsetMap) // Base case: add "" to map
-> generateSubsets("", "b", subsetMap) // Base case: add "b" to map
-> generateSubsets("b", "a", subsetMap)
-> generateSubsets("", "a", subsetMap) // Base case: add "a" to map
-> generateSubsets("", "ab", subsetMap) // Base case: add "ab" to map
-> generateSubsets("ab", "a", subsetMap)
-> generateSubsets("b", "a", subsetMap)
-> generateSubsets("", "a", subsetMap) // Base case: add "a" to map
-> generateSubsets("", "ab", subsetMap) // Base case: add "ab" to map
-> generateSubsets("b", "aa", subsetMap)
-> generateSubsets("", "aa", subsetMap) // Base case: add "aa" to map
-> generateSubsets("", "aab", subsetMap) // Base case: add "aab" to map

Output for input "aab":

""
"a"
"aa"
"aab"
"ab"
"b"

Explanation of the Map:

The map after recursion would contain the following entries:

{"": 1, "a": 2, "aa": 1, "aab": 1, "ab": 1, "b": 1}

After sorting the keys of the map, the subsets are printed in lexicographical order.

Time Complexity:

Recursion: The recursion explores all subsets, which results in 2^n possible subsets, where n is the length of the input string.

Map Operations: Each subset insertion into the map takes O(1) time for each subset.

Sorting: After generating all subsets, we sort the map's keys, which takes O(k log k) time, where k is the number of unique subsets (k <= 2^n).

Thus, the total time complexity is approximately:

Recursion: O(2^n)

Sorting: O(k log k) where k = 2^n

So the total time complexity is O(2^n * n).

Conclusion:

This solution generates unique subsets of the input string using recursion and stores the results in a Map. It ensures that only unique subsets are stored and then prints them in lexicographical order. The approach uses recursion and avoids handling individual characters explicitly by leveraging the map to track uniqueness.

6

Reply