Generate All Subsets Powerset in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation with duplicates

What is the output of the following Java code that generates all subsets (powerset) of the array [1, 2, 2]?

DSA Java

import java.util.*;
public class Main {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private static void backtrack(int[] nums, int start, List<Integer> tempList, List<List<Integer>> result) {
        result.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            tempList.add(nums[i]);
            backtrack(nums, i + 1, tempList, result);
            tempList.remove(tempList.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        List<List<Integer>> subsets = subsetsWithDup(nums);
        System.out.println(subsets);
    }
}

A [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

B [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

C [[], [1], [2], [2, 2], [1, 2], [1, 2, 2], [2, 2, 2]]

D [[], [1], [1, 2], [2], [2, 2], [1, 2, 2], [2, 2, 2]]

💡 Hint

Duplicates are skipped to avoid repeated subsets. The subsets are generated in sorted order.

The code sorts the array and skips duplicates during recursion to avoid repeated subsets. The output lists all unique subsets including empty set.

❓ Predict Output

intermediate

Output of powerset generation for empty input

What is the output of this Java code that generates all subsets of an empty array?

DSA Java

import java.util.*;
public class Main {
    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 start, List<Integer> tempList, List<List<Integer>> result) {
        result.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            backtrack(nums, i + 1, tempList, result);
            tempList.remove(tempList.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {};
        List<List<Integer>> subsets = subsets(nums);
        System.out.println(subsets);
    }
}

A [[], []]

B [[]]

C []

D null

💡 Hint

The powerset of an empty set contains only the empty set.

Even for an empty input, the powerset contains one subset: the empty subset.

🔧 Debug

advanced

Identify the error in powerset generation code

What error does the following Java code produce when generating all subsets of [1, 2]?

DSA Java

import java.util.*;
public class Main {
    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 start, List<Integer> tempList, List<List<Integer>> result) {
        result.add(tempList);
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            backtrack(nums, i + 1, tempList, result);
            tempList.remove(tempList.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2};
        List<List<Integer>> subsets = subsets(nums);
        System.out.println(subsets);
    }
}

A Compilation error due to missing return statement

B NullPointerException at runtime

C StackOverflowError due to infinite recursion

D The output contains multiple references to the same list, causing all subsets to appear as [1, 2]

💡 Hint

Check how subsets are added to the result list.

The code adds the same list reference (tempList) multiple times without copying it, so all entries in result point to the same list which ends up as [1, 2].

❓ Predict Output

advanced

Output of iterative powerset generation

What is the output of this Java code that generates all subsets of [1, 2, 3] using an iterative approach?

DSA Java

import java.util.*;
public class Main {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        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;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> subsets = subsets(nums);
        System.out.println(subsets);
    }
}

A [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

B [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]

C [[], [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

D [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

💡 Hint

The subsets are generated by adding each number to all existing subsets.

The iterative method starts with empty subset and adds each number to all existing subsets, preserving order of generation.

🧠 Conceptual

expert

Number of subsets generated by powerset algorithm

Given an input array of length n, how many subsets does the powerset generation algorithm produce?

A n

B n^2

C 2^n

D n!

💡 Hint

Each element can either be included or excluded in a subset.

For each element, there are two choices: include or exclude. So total subsets are 2 multiplied by itself n times = 2^n.

Practice

1. What does the term powerset mean in the context of subsets?

easy

A. All possible subsets of a given set, including empty and full set

B. Only the subsets with exactly two elements

C. The set of elements that are not in the original set

D. The largest subset of a given set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all possible subsets, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets of a given set, including empty and full set correctly describes the powerset as all subsets. Other options describe partial or unrelated concepts.

3. Final Answer:

   All possible subsets of a given set, including empty and full set -> Option A

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset possible, including empty [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Assuming powerset means complement sets

2. Which of the following Java method signatures correctly represents a function that returns all subsets of an integer array?

easy

A. public int generateSubsets(int[] nums)

B. public void generateSubsets(int[] nums)

C. public List generateSubsets(int[] nums)

D. public List<Integer> generateSubsets(int nums)

Solution

1. Step 1: Identify return type for all subsets

   All subsets of an integer array require returning a list of lists of integers, so return type should be List.

2. Step 2: Check method parameters and return type

   public List generateSubsets(int[] nums) matches correct return type and parameter. Options A and C have wrong return types, and D has wrong parameter type.

3. Final Answer:

   public List<List<Integer>> generateSubsets(int[] nums) -> Option C

4. Quick Check:

   Return type must hold all subsets = List of List [OK]

Hint: Return type for subsets is List of List of Integers [OK]

Common Mistakes:

• Using int return type instead of list
• Using void return type without output
• Passing single int instead of int array

3. What is the output of the following Java code snippet?

public static List subsets(int[] nums) {
    List result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> subset = new ArrayList<>(result.get(i));
            subset.add(num);
            result.add(subset);
        }
    }
    return result;
}

// Called with nums = {1, 2}

medium

A. [[], [1], [2], [1, 2]]

B. [[1], [2], [1, 2]]

C. [[], [1, 2]]

D. [[1], [2]]

Solution

1. Step 1: Initialize result with empty subset

   Initially, result = [[]].

2. Step 2: Iterate over nums and add new subsets

   For num=1, add [1] to result: result = [[], [1]]. For num=2, add [2] and [1,2]: result = [[], [1], [2], [1, 2]].

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option A

4. Quick Check:

   All subsets of {1,2} = [[], [1], [2], [1, 2]] [OK]

Hint: Start with empty set, add each number to existing subsets [OK]

Common Mistakes:

• Forgetting to include empty subset
• Adding subsets in wrong order
• Missing combined subsets like [1, 2]

4. Identify the error in the following Java code that attempts to generate all subsets of an integer array:

public static List subsets(int[] nums) {
    List result = new ArrayList<>();
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> subset = new ArrayList<>(result.get(i));
            subset.add(num);
            result.add(subset);
        }
    }
    result.add(new ArrayList<>());
    return result;
}

medium

A. The input array should be converted to a list first

B. The inner loop should run from size-1 to 0

C. The method should return an int, not a list

D. Empty subset is added at the end, should be added before loop

Solution

1. Step 1: Check when empty subset is added

   Empty subset must be added before starting to build subsets, so that initial subsets exist.

2. Step 2: Analyze code flow

   Here, empty subset is added after loops, so result.size() is zero initially and inner loop never runs, producing empty result except empty subset at end.

3. Final Answer:

   Empty subset is added at the end, should be added before loop -> Option D

4. Quick Check:

   Empty subset must be first for subsets to build [OK]

Hint: Add empty subset before loops to start building subsets [OK]

Common Mistakes:

• Adding empty subset after loops
• Incorrect loop ranges causing no subsets
• Returning wrong data type

5. Given an integer array nums that may contain duplicates, which modification to the standard subsets generation algorithm ensures the powerset contains no duplicate subsets?

hard

A. Only generate subsets of fixed size to avoid duplicates

B. Sort the array first and skip adding subsets that duplicate the last added subset

C. Generate subsets normally without changes; duplicates are automatically handled

D. Use a HashSet to store subsets and convert back to list at the end

Solution

1. Step 1: Understand duplicates in subsets

   Duplicates in input cause duplicate subsets if not handled.

2. Step 2: Use sorting and skip duplicates

   Sorting groups duplicates together. While generating subsets, skip adding subsets that duplicate the last added subset to avoid duplicates.

3. Final Answer:

   Sort the array first and skip adding subsets that duplicate the last added subset -> Option B

4. Quick Check:

   Sort + skip duplicates = unique subsets [OK]

Hint: Sort input and skip duplicates during subset generation [OK]

Common Mistakes:

• Ignoring duplicates causing repeated subsets
• Using HashSet but forgetting order or conversion
• Assuming duplicates don't affect subsets