Subset Generation
Subset Idea
Generating all subsets of a set means producing every possible combination of its elements, including the empty set and the full set itself. It's a foundational technique that shows up whenever a problem asks you to consider 'every possible selection' of items.
Example: Subset Idea
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> set = {1, 2};
cout << "{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set");
}
}print("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set")#include <stdio.h>
int main() {
printf("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set");
return 0;
}Login to try C/C++/Java code in the editor
Include or Exclude
The core recursive idea is a binary choice at each element: either include it in the current subset being built, or skip it, and recurse into the remaining elements either way. Every complete path of include/skip decisions produces one distinct subset.
Example: Include or Exclude
#include <iostream>
#include <vector>
using namespace std;
void subsets(vector<int>& nums, int i, vector<int>& cur) {
if (i == nums.size()) {
cout << "{ "; for (int x : cur) cout << x << " "; cout << "}" << endl;
return;
}
subsets(nums, i + 1, cur);
cur.push_back(nums[i]);
subsets(nums, i + 1, cur);
cur.pop_back();
}
int main() {
vector<int> nums = {1, 2};
vector<int> cur;
subsets(nums, 0, cur);
return 0;
}import java.util.*;
public class Main {
static void subsets(int[] nums, int i, List<Integer> cur) {
if (i == nums.length) { System.out.println(cur); return; }
subsets(nums, i + 1, cur);
cur.add(nums[i]);
subsets(nums, i + 1, cur);
cur.remove(cur.size() - 1);
}
public static void main(String[] args) {
subsets(new int[]{1, 2}, 0, new ArrayList<>());
}
}def subsets(nums, i, cur):
if i == len(nums):
print(cur)
return
subsets(nums, i + 1, cur)
cur.append(nums[i])
subsets(nums, i + 1, cur)
cur.pop()
subsets([1, 2], 0, [])#include <stdio.h>
int cur[10], top = 0;
void subsets(int nums[], int i, int n) {
if (i == n) {
printf("{ "); for (int j = 0; j < top; j++) printf("%d ", cur[j]); printf("}\n");
return;
}
subsets(nums, i + 1, n);
cur[top++] = nums[i];
subsets(nums, i + 1, n);
top--;
}
int main() {
int nums[] = {1, 2};
subsets(nums, 0, 2);
return 0;
}Login to try C/C++/Java code in the editor
Recursive Generation
Recursion naturally models this by processing one element per call and moving to the next element regardless of which choice was made, until every element has been decided on and a complete subset is recorded.
Example: Recursive Generation
#include <iostream>
#include <vector>
using namespace std;
int count = 0;
void subsets(vector<int>& nums, int i, vector<int>& cur) {
if (i == nums.size()) { count++; return; }
subsets(nums, i + 1, cur);
cur.push_back(nums[i]);
subsets(nums, i + 1, cur);
cur.pop_back();
}
int main() {
vector<int> nums = {1, 2, 3};
vector<int> cur;
subsets(nums, 0, cur);
cout << "Total subsets generated: " << count;
return 0;
}import java.util.*;
public class Main {
static int count = 0;
static void subsets(int[] nums, int i, List<Integer> cur) {
if (i == nums.length) { count++; return; }
subsets(nums, i + 1, cur);
cur.add(nums[i]);
subsets(nums, i + 1, cur);
cur.remove(cur.size() - 1);
}
public static void main(String[] args) {
subsets(new int[]{1, 2, 3}, 0, new ArrayList<>());
System.out.println("Total subsets generated: " + count);
}
}count = 0
def subsets(nums, i, cur):
global count
if i == len(nums):
count += 1
return
subsets(nums, i + 1, cur)
cur.append(nums[i])
subsets(nums, i + 1, cur)
cur.pop()
subsets([1, 2, 3], 0, [])
print("Total subsets generated:", count)#include <stdio.h>
int cur[10], top = 0, count = 0;
void subsets(int nums[], int i, int n) {
if (i == n) { count++; return; }
subsets(nums, i + 1, n);
cur[top++] = nums[i];
subsets(nums, i + 1, n);
top--;
}
int main() {
int nums[] = {1, 2, 3};
subsets(nums, 0, 3);
printf("Total subsets generated: %d", count);
return 0;
}Login to try C/C++/Java code in the editor
Subset Properties
Because each of the n elements independently can be either included or excluded, there are exactly 2^n possible subsets — this exponential count is why subset generation is only practical for relatively small input sizes.
Example: Subset Properties
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n = 5;
cout << n << " elements produce " << (int)pow(2, n) << " subsets";
return 0;
}public class Main {
public static void main(String[] args) {
int n = 5;
System.out.println(n + " elements produce " + (int) Math.pow(2, n) + " subsets");
}
}n = 5
print(n, "elements produce", 2 ** n, "subsets")#include <stdio.h>
#include <math.h>
int main() {
int n = 5;
printf("%d elements produce %d subsets", n, (int)pow(2, n));
return 0;
}Login to try C/C++/Java code in the editor
Practice
This same include-or-exclude recursive pattern is the direct ancestor of harder problems like the 0/1 knapsack and combination-sum problems, which add constraints (like a weight limit or target sum) on top of the same basic subset-generation structure.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum");
}
}print("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum")#include <stdio.h>
int main() {
printf("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: