Recommend reading at at Notion where it was originally published.
Writing blog is much fun at Notion. Dev blog is no match to Notion.
Will edit here later.
For a given array int[] nums = {1,2,3} generate all 2n power sets where 𝑛 = length of given array.
Defn : power set is a maximal set comprising of all subsequences (the order of element is preserved)
PS (nums) = [ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ]
Motivation for the notes :
LeetCodeSubsets - LeetCode
Power Set | Practice | GeeksforGeeks
There are broadly two approaches :
- Bit Masking (iterative)
- Backtracking (recursive) 2a. Include-Exclude paradigm : here we see two variants & why we should use one over other 2b. For-loop paradigm : prefer this (reason at the end)
👉 Apply your learning :
How to generate all subsequences of length ≤ 𝑘 , where 𝑘 ≤ 𝑛 (length of the nums array). see solution
Bit Masking
public class PowerSet {
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
int totalSubsets = 1 << n; // 2^n
List<List<Integer>> powerSet = new ArrayList<>();
for (int mask = 0; mask < totalSubsets; mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) { // Check if the i-th bit is set
subset.add(nums[i]);
}
}
powerSet.add(subset);
}
return powerSet;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
PowerSet ps = new PowerSet();
System.out.println(ps.subsets(nums));
}
}
Back tracking
Some basics need to be made clear before proceeding with the code :
Meaning of Backtracking : lit. retrace one's steps. It means undoing changes made in previous function call. In world of backtracking at every step we are faced with two choices : Take (include) & Not Take (exclude). Both those choices need to be reflected in final result set. But for current index if we take (i.e. add to current list) then we need to remove that element from list.
Pass by Value vs Pass by Reference : In Java everything* is pass by reference. Unlike C/C++ , except for primitives, no object is passed by value(copy). All objects (for this article, List) are passed by reference. This implies changes made to the object in any called function is also refected in the calling function. To stop this and achieve backtracking
Because of Pass-By-Reference nature of Java, we need to add copy of list to final result set.
There are two broad paradigms for generating subsequences using recursion:
Include-Exclude Paradigm (Recursive Branching) :
At each step, decide whether to include or exclude the current element from the subsequence.
This approach directly models the binary decision tree (include/exclude) for each element.
For-Loop Paradigm (Iterative Expansion with Recursion) :
At each recursive call, iterate through the elements starting from the current index and recursively expand subsequences by including elements.
B1. Include-Exclude paradigm
This paradigm uses ‘currentIndex’ as recursive function argument. There are two ways to achieve this
Copying in temporary list before calling : saveCopy-include-exclude-add Model
In this approach, for the base case we add the list received in argument in the result directly. Before we modify the list by adding a current element, store the original list to preserve how the list would have looked had the current element been skipped, i.e. not added to the list.
class Solution {
public List> subsets(int[] nums) {
List> result = new ArrayList<>();
generateSubsets(nums, 0, result, new ArrayList());
return (result);
}
public void generateSubsets(int[] nums, int i, List<List<Integer>> result, List<Integer> list) {
// Base case : when index i gets out of bound - pack the result
if(i == nums.length) {
result.add(list);
return;
}
// INCLUDE nums[i]
List <Integer> tempList = new ArrayList<>(list); //make temporary COPY
list.add(nums[i]); // before the list is modified
generateSubsets(nums, i+1, result, list); //ADD i-th element
// EXCLUDE nums[i]
generateSubsets(nums, i+1, result, tempList); //SKIP i-th element : temporary list copy used
}
}
Note : One might think that that writing Exclude case before writing Include case (see code below) might obviate the need to copy. But it does not. Why? Think 🤔!!!
// incorrect function
public void generateSubsets(int[] nums, int i, List> result, List list) {
if (i == nums.length) {
result.add(new ArrayList<>(list));
return;
}
//EXCLUDE
generateSubsets(nums, i + 1, result, list);
//INCLUDE
list.add(nums[i]);
generateSubsets(nums, i + 1, result, list); //DOES NOT WORK
}
// int[] nums = {1, 2, 3};
// Output : [[],[3],[3,2],[3,2,3],[3,2,3,1],[3,2,3,1,3],[3,2,3,1,3,2],[3,2,3,1,3,2,3]]
Copying the list to the result : include-exclude-addCopy model
In this case, rather than directly adding list (to the result set) received the argument, we only add the copy of the list. This approach is more memory-efficient since it avoids unnecessary list copies.
public class PowerSet {
public List> subsets(int[] nums) {
List> powerSet = new ArrayList<>();
generateSubsets(nums, 0, new ArrayList<>(), powerSet);
return powerSet;
}
private void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> powerSet) {
if (index == nums.length) {
powerSet.add(new ArrayList<>(current)); //Add current subset
return;
}
// INCLUDE the current element
current.add(nums[index]);
generateSubsets(nums, index + 1, current, powerSet);
// Backtrack: Remove the last added element to explore the "EXCLUDE" case
current.remove(current.size() - 1);
generateSubsets(nums, index + 1, current, powerSet);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
PowerSet ps = new PowerSet();
System.out.println(ps.subsets(nums));
}
}
Again, alternatively, you can interchange the order of include & exclude snippet :
private void generateSubsets(int index, int[] nums, List current, List> powerSet) {
if (index == nums.length) {
powerSet.add(new ArrayList<>(current)); // Add current subset
return;
}
// Exclude
generateSubsets(index + 1, nums, current, powerSet);
// Include
current.add(nums[index]);
generateSubsets(index + 1, nums, current, powerSet);
// Backtrack to remove the last added element
current.remove(current.size() - 1);
}
B2. For-loop paradigm
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
generate(nums, 0, new ArrayList<Integer>(), result);
return (result);
}
private void generate(int[] nums, int index, List<Integer> current, List<List<Integer>> subsequences) {
subsequences.add(new ArrayList<>(current)); // Add current subsequence
for (int i = index; i < nums.length; i++) {
current.add(nums[i]); // Include nums[i]
generate(nums, i + 1, current, subsequences); //Recurse for the next elements
current.remove(current.size() - 1); // Backtrack
}
}
}
Here, we need not have base case as the index boundation is implicitly checked by the for loop.
Logic:
Add the current subsequence to the result list.
If the size of the current subsequence exceeds array size, stop further recursion (return).
Iterate through all elements starting from index. For each element:
Add it to the current subsequence.
Recursively process the next elements.
Backtrack by removing the last added element.
Efficiency and Practical Implications:
Include-Exclude Paradigm generates exactly 2 recursive calls for each element. This can result in unnecessary calls where the same subsequences are generated repeatedly (e.g., excluding an already excluded element).
Efficiency bottleneck: More recursive calls lead to slightly higher runtime overhead.
Use case: Simple subset generation, where performance is not critical.
For-Loop Paradigm systematically expands subsequences by iterating and branching only once per element. This avoids redundant calls because each recursive branch handles a unique set of elements.
Efficiency improvement: Fewer recursive calls and reduced overhead compared to include-exclude.
Use case: Subsequence generation with constraints (e.g., size
≤
k
≤k, lexicographical order).
Solution to Problem :
public class SubsequenceGenerator {
public List> generateSubsequences(int[] nums, int k) {
List> subsequences = new ArrayList<>();
generate(0, nums, new ArrayList<>(), subsequences, k);
return subsequences;
}
private void generate(int index, int[] nums, List<Integer> current, List<List<Integer>> subsequences, int k) {
if (current.size() > k) {
return; // Stop if the current subset exceeds the desired length
}
subsequences.add(new ArrayList<>(current)); // Add current subsequence
for (int i = index; i < nums.length; i++) {
current.add(nums[i]); // Include nums[i]
generate(i + 1, nums, current, subsequences, k); // Recurse for the next elements
current.remove(current.size() - 1); // Backtrack
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int k = 2; // Maximum length of subsequences
SubsequenceGenerator generator = new SubsequenceGenerator();
List<List<Integer>> result = generator.generateSubsequences(nums, k);
System.out.println(result);
}
}
TAKE AWAY :
public List<List<Integer>> subsets(Type linear_ds) {//int[] , List<> , String ...
List<List<Integer>> result;
generate(linear_ds, 0, new ArrayList<Integer>(), result);
return (result);
}
void generate(int[] n, int idx, List<Integer> current, List<List<Integer>> result) {
// Add current subsequence to result
// FOR i = [idx, n.length)
// CHOOSE : include n[i] in current subsequence
// EXPORE : generate(nums, i+1, current, result)
// BACKTRACK : exclude n[i] from current subsequence
}
Top comments (0)