Power Set

Given a set of n distinct elements, the power set is the set of all possible subsets, including the empty set and the set itself.

Your task is to generate and return all subsets of the given set.

Understanding the Problem

We are given a set of n distinct elements, and we are asked to generate its power set. A power set is the collection of all possible subsets that can be formed from the given set — including the empty set and the set itself.

For example, if the input set is [a, b], the power set would be [[], [a], [b], [a, b]].

This is a common problem in combinatorics and programming, and it can be solved efficiently using bit manipulation.

Step-by-Step Solution with Example

Step 1: Understand how subsets relate to binary numbers

Each element in the original set has two choices: either it is present in a subset or it is not. So, for n elements, there are 2^n possible combinations — which means 2^n subsets.

We can represent each subset using a binary number where the i-th bit tells whether to include the i-th element.

Step 2: Take an example set [1, 2, 3]

The size of the input set is 3, so total subsets = 2^3 = 8. We loop from 0 to 7, and for each number, we check its binary representation.

• 0 → 000 → []
• 1 → 001 → [3]
• 2 → 010 → [2]
• 3 → 011 → [2, 3]
• 4 → 100 → [1]
• 5 → 101 → [1, 3]
• 6 → 110 → [1, 2]
• 7 → 111 → [1, 2, 3]

We interpret each bit from right to left (LSB to MSB) and use it to decide whether to include the corresponding element from the input set.

Step 3: Implement the logic in code

def power_set(nums):
    n = len(nums)
    result = []
    total = 1 << n  # 2^n subsets

    for mask in range(total):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)

    return result

# Example:
print(power_set([1, 2, 3]))

Edge Cases

• Empty Set: If the input is [], the power set should return [[]].
• Single Element: Input [x] should return [[], [x]].
• Large Input Size: Since total subsets = 2^n, be careful if n is large (e.g., > 20), as it could cause performance or memory issues.

Final Thoughts

This problem gives a great opportunity to practice bit manipulation and understand how binary numbers can represent subset selections. It's also a common pattern in backtracking and dynamic programming problems.

By understanding this step-by-step process, even beginners can break down and solve more complex combinatorics problems later on.

1. The total number of subsets for a set of size n is 2^n.
2. Loop through all numbers from 0 to 2^n - 1. Each number represents a subset.
3. For each number, check the binary representation. If the j-th bit is set, include the j-th element of the original set in the current subset.
4. Collect all such subsets into the result list.

#include <stdio.h>
#include <math.h>

void printPowerSet(int* set, int set_size) {
    unsigned int pow_set_size = 1 << set_size; // 2^n
    int counter, j;

    for(counter = 0; counter < pow_set_size; counter++) {
        printf("{ ");
        for(j = 0; j < set_size; j++) {
            if (counter & (1 << j)) {
                printf("%d ", set[j]);
            }
        }
        printf("}\n");
    }
}

int main() {
    int set[] = {1, 2, 3};
    int set_size = sizeof(set)/sizeof(set[0]);
    printPowerSet(set, set_size);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void printPowerSet(const vector<int>& set) {
    int set_size = set.size();
    int pow_set_size = 1 << set_size; // 2^n

    for (int counter = 0; counter < pow_set_size; counter++) {
        cout << "{ ";
        for (int j = 0; j < set_size; j++) {
            if (counter & (1 << j)) {
                cout << set[j] << " ";
            }
        }
        cout << "}\n";
    }
}

int main() {
    vector<int> set = {1, 2, 3};
    printPowerSet(set);
    return 0;
}

def power_set(original_set):
    n = len(original_set)
    power_set_size = 1 << n  # 2^n
    result = []
    for counter in range(power_set_size):
        subset = []
        for j in range(n):
            if counter & (1 << j):
                subset.append(original_set[j])
        result.append(subset)
    return result

# Example usage
my_set = [1, 2, 3]
for subset in power_set(my_set):
    print(subset)

import java.util.*;

public class PowerSet {
    public static List<List<Integer>> powerSet(List<Integer> set) {
        int n = set.size();
        int powSetSize = 1 << n; // 2^n
        List<List<Integer>> result = new ArrayList<>();

        for (int counter = 0; counter < powSetSize; counter++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((counter & (1 << j)) != 0) {
                    subset.add(set.get(j));
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> set = Arrays.asList(1, 2, 3);
        List<List<Integer>> powerSet = powerSet(set);
        for (List<Integer> subset : powerSet) {
            System.out.println(subset);
        }
    }
}

function powerSet(originalSet) {
  const n = originalSet.length;
  const powerSetSize = 1 << n; // 2^n
  const result = [];

  for (let counter = 0; counter < powerSetSize; counter++) {
    const subset = [];
    for (let j = 0; j < n; j++) {
      if ((counter & (1 << j)) !== 0) {
        subset.push(originalSet[j]);
      }
    }
    result.push(subset);
  }

  return result;
}

// Example usage
const set = [1, 2, 3];
const subsets = powerSet(set);
subsets.forEach(subset => console.log(subset));

package main

import "fmt"

func powerSet(set []int) [][]int {
    n := len(set)
    powSetSize := 1 << n
    var result [][]int

    for counter := 0; counter < powSetSize; counter++ {
        var subset []int
        for j := 0; j < n; j++ {
            if (counter & (1 << j)) != 0 {
                subset = append(subset, set[j])
            }
        }
        result = append(result, subset)
    }
    return result
}

func main() {
    set := []int{1, 2, 3}
    subsets := powerSet(set)
    for _, subset := range subsets {
        fmt.Println(subset)
    }
}

fn power_set(set: &[i32]) -> Vec<Vec<i32>> {
    let n = set.len();
    let pow_set_size = 1 << n;
    let mut result = Vec::new();

    for counter in 0..pow_set_size {
        let mut subset = Vec::new();
        for j in 0..n {
            if (counter & (1 << j)) != 0 {
                subset.push(set[j]);
            }
        }
        result.push(subset);
    }

    result
}

fn main() {
    let set = vec![1, 2, 3];
    let subsets = power_set(&set);
    for subset in subsets {
        println!("{:?}", subset);
    }
}

fun powerSet(set: List<Int>): List<List<Int>> {
    val n = set.size
    val powSetSize = 1 << n
    val result = mutableListOf<List<Int>>()

    for (counter in 0 until powSetSize) {
        val subset = mutableListOf<Int>()
        for (j in 0 until n) {
            if ((counter and (1 << j)) != 0) {
                subset.add(set[j])
            }
        }
        result.add(subset)
    }

    return result
}

fun main() {
    val set = listOf(1, 2, 3)
    val subsets = powerSet(set)
    subsets.forEach { println(it) }
}

func powerSet(set: [Int]) -> [[Int]] {
    let n = set.count
    let powSetSize = 1 << n
    var result = [[Int]]()

    for counter in 0 ..< powSetSize {
        var subset = [Int]()
        for j in 0 ..< n {
            if (counter & (1 << j)) != 0 {
                subset.append(set[j])
            }
        }
        result.append(subset)
    }

    return result
}

let set = [1, 2, 3]
let subsets = powerSet(set: set)
for subset in subsets {
    print(subset)
}

function powerSet(set: number[]): number[][] {
  const n = set.length;
  const powSetSize = 1 << n;
  const result: number[][] = [];

  for (let counter = 0; counter < powSetSize; counter++) {
    const subset: number[] = [];
    for (let j = 0; j < n; j++) {
      if ((counter & (1 << j)) !== 0) {
        subset.push(set[j]);
      }
    }
    result.push(subset);
  }

  return result;
}

// Example usage
const set = [1, 2, 3];
const subsets = powerSet(set);
subsets.forEach(subset => console.log(subset));

Time complexity

Space complexity

O(n * 2^n)

The output contains all 2^n subsets, and each subset can contain up to n elements. Hence, the space required to store the result is O(n * 2^n). Additional space usage is minimal compared to the output size.