← Back to DSA Course | Chapter 8: Recursion & Backtracking | Lesson 7 of 7

Subset Generation

Generating subsets is like listing every possible team you could pick from your friends, from nobody at all to everybody.

In this page:

  1. Subset Idea
  2. Include or Exclude
  3. Recursive Generation
  4. Subset Properties
  5. Practice
Syntax
markup 
def subsets(index, current):
    if index == len(nums):
        result.append(current[:])
        return
    subsets(index + 1, current)          # exclude
    current.append(nums[index])
    subsets(index + 1, current)          # include
    current.pop()

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;
}

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;
}

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;
}

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;
}

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;
}
Related Topics

Sudoku Solver · N-Queens Problem · Backtracking Introduction · Tower of Hanoi

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Adding cur to the result without copying it and then continuing to change it.
  2. Forgetting to remove the element after the include branch (backtracking), so later subsets contain extra items.
  3. Missing the empty subset or expecting fewer than 2^n subsets.
Chapter Summary
  • Recursion solves problems by breaking them into smaller versions of themselves, as in Fibonacci, factorial, and Tower of Hanoi.
  • Backtracking tries choices and undoes them when they fail.
  • N-Queens, Sudoku Solver, and subset generation are classic backtracking problems.
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Sudoku Solver Next Lesson → Bubble Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.