Essential Algorithms: Finding Subsets

Introduction

When delving into the world of programming, certain problems are foundational to build up to complex problems. The Subset problem is one such challenge. In this post we will dive into the intricacies of the Subset problem and tackle it in C++.

Problem Statement

Before diving into the solution, let's understand the problem statement. Given a set of integers X find all subsets of X.

Solution

The best way to think about this problem is in terms of bits. I'm going give you most of the solution up front so we can explain it throughout this article.

All possible subsets of a set with N items exist as the binary representation of the numbers of 0 up to 2^N

Ok let me explain this statement. Lets say we have a set X = {A, B, C, D}. We want to find all possible subsets of X. Using our thesis, lets find all the subsets. First we will look at all the numbers from 0 to 2^N in binary.

Integer	Binary	Integer	Binary	Integer	Binary	Integer	Binary
0	0000	4	0100	8	1000	12	1100
1	0001	5	0101	9	1001	13	1101
2	0010	6	0110	10	1010	14	1110
3	0011	7	0111	11	1011	15	1111

Thats a lot of numbers but how can we use this? Well look at the positions of the 1 bits in the binary numbers. If each number is a subset, a 1 in the binary number means you should include that item in the subset. For example, in 0000 there are no 1 bits so it represents the empty set. However in 0110 (aka 6), there are 2 1 bits, and that would represent the subset {B, C}.

To solve the subset sum problem, we need to get the position of the 1 bits in each number and check if that subset sums to the target. Lets code that in C++.

The Code

                        
#include <iostream>
#include <vector>

void printAllSubsets(const std::vector& set) {
    int n = set.size();

    // Total number of subsets is 2^n
    int totalSubsets = 1 << n;

    std::cout << "All subsets of the given set:\n";
    for (int subset = 0; subset < totalSubsets; ++subset) {
        std::cout << "{ ";

        for (int i = 0; i < n; ++i) {
            // Check if the i-th bit is set in the subset bitmask
            if (subset & (1 << i)) {
                std::cout << set[i] << " ";
            }
        }

        std::cout << "}\n";
    }
}

int main() {
    std::vector set = {1, 2, 3};

    printAllSubsets(set);

    return 0;
}

Conclusion

This is a very helpful introduction to bitwise algorithms. Generating all subsets can be a very useful as a building block for solving more complex problems. I have used this idea for multiple competitive programming problems. I hope it benefits you on your coding journey as well.