Power Set

Definition

Definition

The Power Set Algorithm is a method used to generate all possible subsets of a given set. It's commonly implemented using recursion and bitwise manipulation for efficiency

Explanation

Start with an empty set and iteratively adds elements from the original set, effectively doubling the number of subsets with each addition. It utilizes recursion to explore all possible combinations. By leveraging bitwise manipulation, it efficiently generates subsets by representing each subset as a binary number, where each bit position corresponds to an element in the set

Guidance

• Start with an empty set (result) and an integer variable (n) representing the size of the input set
• Use a loop to iterate from 0 to $2^{n-1}$
• Within the loop, for each iteration, convert the current loop variable into a binary representation
• For each bit in the binary representation, if the bit is set (1), add the corresponding element from the input set to the result set
• Add the generated subset to the final result set
• Repeat until all possible subsets are generated

Tips

• utilize bitwise manipulation to efficiently represent subsets
• use memoization techniques if necessary to optimize performance for larger input sets

Practice

Practice

powerSet(inputSet):
  memo = {} # Initialize a memoization dictionary to store already computed subsets
  result = [] # Initialize an empty list to store subsets

  generateSubset(0, []) # Start the recursive function with index 0 and an empty subset
  return result # Return the power set

# Recursive function to generate subsets
generateSubset(index, currentSubset):
  if index == len(inputSet): # Base case: If index equals the length of input set
    result.append(currentSubset) # Add currentSubset to result list
    return
  if (index, currentSubset) in memo: # Check if subset with current index and currentSubset is memoized
    return
  generateSubset(index + 1, currentSubset) # Skip current element
  generateSubset(index + 1, currentSubset + [inputSet[index]]) # Include current element
  memo[(index, currentSubset)] = True # Memoize the current subset

Solution

package main

func backtrackingPowerSetRecursive(originalSet []int, allSubsets [][]int, currentSubSet []int, startAt int) [][]int {
	for position := startAt; position < len(originalSet); position++ {
		currentSubSet = append(currentSubSet, originalSet[position])
		allSubsets = append(allSubsets, append([]int{}, currentSubSet...))

		allSubsets = backtrackingPowerSetRecursive(originalSet, allSubsets, currentSubSet, position+1)

		currentSubSet = currentSubSet[:len(currentSubSet)-1]
	}

	return allSubsets
}

func bitwisePowerSet(originalSet []int) [][]int {
	var subSets [][]int
	numberOfCombinations := 1 << len(originalSet)

	for combinationIndex := 0; combinationIndex < numberOfCombinations; combinationIndex++ {
		var subSet []int

		for setElementIndex := 0; setElementIndex < len(originalSet); setElementIndex++ {
			if combinationIndex&(1<<setElementIndex) != 0 {
				subSet = append(subSet, originalSet[setElementIndex])
			}
		}

		subSets = append(subSets, subSet)
	}

	return subSets
}

func cascadingPowerSet(originalSet []int) [][]int {
	sets := [][]int{{}}

	for numIdx := 0; numIdx < len(originalSet); numIdx++ {
		existingSetsNum := len(sets)

		for setIdx := 0; setIdx < existingSetsNum; setIdx++ {
			set := append([]int{}, sets[setIdx]...)
			set = append(set, originalSet[numIdx])
			sets = append(sets, set)
		}
	}

	return sets
}

import java.util.ArrayList;
import java.util.List;

public class PowerSet {

  public static List<List<Integer>> backtrackingPowerSetRecursive(int[] originalSet) {
    List<List<Integer>> allSubsets = new ArrayList<>();
    allSubsets.add(new ArrayList<>());
    backtrackingPowerSetRecursive(originalSet, allSubsets, new ArrayList<>(), 0);
    return allSubsets;
  }

  private static void backtrackingPowerSetRecursive(int[] originalSet, List<List<Integer>> allSubsets, List<Integer> currentSubSet, int startAt) {
    for (int position = startAt; position < originalSet.length; position++) {
      currentSubSet.add(originalSet[position]);
      allSubsets.add(new ArrayList<>(currentSubSet));

      backtrackingPowerSetRecursive(originalSet, allSubsets, currentSubSet, position + 1);

      currentSubSet.remove(currentSubSet.size() - 1);
    }
  }

  public static List<List<Integer>> bitwisePowerSet(int[] originalSet) {
    List<List<Integer>> subSets = new ArrayList<>();
    int numberOfCombinations = 1 << originalSet.length;

    for (int combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex++) {
      List<Integer> subSet = new ArrayList<>();

      for (int setElementIndex = 0; setElementIndex < originalSet.length; setElementIndex++) {
        if ((combinationIndex & (1 << setElementIndex)) != 0) {
          subSet.add(originalSet[setElementIndex]);
        }
      }

      subSets.add(subSet);
    }

    return subSets;
  }

  public static List<List<Integer>> cascadingPowerSet(int[] originalSet) {
    List<List<Integer>> sets = new ArrayList<>();
    sets.add(new ArrayList<>());

    for (int numIdx = 0; numIdx < originalSet.length; numIdx++) {
      int existingSetsNum = sets.size();

      for (int setIdx = 0; setIdx < existingSetsNum; setIdx++) {
        List<Integer> set = new ArrayList<>(sets.get(setIdx));
        set.add(originalSet[numIdx]);
        sets.add(set);
      }
    }

    return sets;
  }
}

function backtrackingPowerSetRecursive(
  originalSet,
  allSubsets = [[]],
  currentSubSet = [],
  startAt = 0,
) {
  for (let position = startAt; position < originalSet.length; position += 1) {
    currentSubSet.push(originalSet[position]);
    allSubsets.push([...currentSubSet]);

    backtrackingPowerSetRecursive(
      originalSet,
      allSubsets,
      currentSubSet,
      position + 1,
    );

    currentSubSet.pop();
  }

  return allSubsets;
}

function bitwisePowerSet(originalSet) {
  const subSets = [];
  const numberOfCombinations = 2 ** originalSet.length;

  for (
    let combinationIndex = 0;
    combinationIndex < numberOfCombinations;
    combinationIndex += 1
  ) {
    const subSet = [];

    for (
      let setElementIndex = 0;
      setElementIndex < originalSet.length;
      setElementIndex += 1
    ) {
      if (combinationIndex & (1 << setElementIndex)) {
        subSet.push(originalSet[setElementIndex]);
      }
    }

    subSets.push(subSet);
  }

  return subSets;
}

function cascadingPowerSet(originalSet) {
  const sets = [[]];

  for (let numIdx = 0; numIdx < originalSet.length; numIdx += 1) {
    const existingSetsNum = sets.length;

    for (let setIdx = 0; setIdx < existingSetsNum; setIdx += 1) {
      const set = [...sets[setIdx], originalSet[numIdx]];
      sets.push(set);
    }
  }

  return sets;
}

fun backtrackingPowerSetRecursive(originalSet: IntArray, allSubsets: MutableList<MutableList<Int>> = mutableListOf(mutableListOf()), currentSubSet: MutableList<Int> = mutableListOf(), startAt: Int = 0): MutableList<MutableList<Int>> {
    for (position in startAt until originalSet.size) {
        currentSubSet.add(originalSet[position])
        allSubsets.add(currentSubSet.toMutableList())

        backtrackingPowerSetRecursive(originalSet, allSubsets, currentSubSet, position + 1)

        currentSubSet.removeAt(currentSubSet.size - 1)
    }

    return allSubsets
}

fun bitwisePowerSet(originalSet: IntArray): MutableList<MutableList<Int>> {
    val subSets = mutableListOf<MutableList<Int>>()
    val numberOfCombinations = 1 shl originalSet.size

    for (combinationIndex in 0 until numberOfCombinations) {
        val subSet = mutableListOf<Int>()

        for (setElementIndex in 0 until originalSet.size) {
            if (combinationIndex and (1 shl setElementIndex) != 0) {
                subSet.add(originalSet[setElementIndex])
            }
        }

        subSets.add(subSet)
    }

    return subSets
}

fun cascadingPowerSet(originalSet: IntArray): MutableList<MutableList<Int>> {
    val sets = mutableListOf<MutableList<Int>>(mutableListOf())

    for (numIdx in originalSet.indices) {
        val existingSetsNum = sets.size

        for (setIdx in 0 until existingSetsNum) {
            val set = mutableListOf<Int>().apply { addAll(sets[setIdx]) }
            set.add(originalSet[numIdx])
            sets.add(set)
        }
    }

    return sets
}

def backtracking_power_set_recursive(original_set, all_subsets=[[]], current_sub_set=[], start_at=0):
    for position in range(start_at, len(original_set)):
        current_sub_set.append(original_set[position])
        all_subsets.append(current_sub_set[:])

        backtracking_power_set_recursive(
            original_set, all_subsets, current_sub_set, position + 1
        )

        current_sub_set.pop()

    return all_subsets


def bitwise_power_set(original_set):
    sub_sets = []
    number_of_combinations = 2 ** len(original_set)

    for combination_index in range(number_of_combinations):
        sub_set = []

        for set_element_index in range(len(original_set)):
            if combination_index & (1 << set_element_index):
                sub_set.append(original_set[set_element_index])

        sub_sets.append(sub_set)

    return sub_sets


def cascading_power_set(original_set):
    sets = [[]]

    for num_idx in range(len(original_set)):
        existing_sets_num = len(sets)

        for set_idx in range(existing_sets_num):
            set_ = sets[set_idx] + [original_set[num_idx]]
            sets.append(set_)

    return sets

fn backtracking_power_set_recursive(original_set: &[i32], all_subsets: &mut Vec<Vec<i32>>, current_sub_set: &mut Vec<i32>, start_at: usize) {
    for position in start_at..original_set.len() {
        current_sub_set.push(original_set[position]);
        all_subsets.push(current_sub_set.clone());

        backtracking_power_set_recursive(original_set, all_subsets, current_sub_set, position + 1);

        current_sub_set.pop();
    }
}

fn backtracking_power_set(original_set: &[i32]) -> Vec<Vec<i32>> {
    let mut all_subsets = vec![vec![]];
    backtracking_power_set_recursive(original_set, &mut all_subsets, &mut vec![], 0);
    all_subsets
}

fn bitwise_power_set(original_set: &[i32]) -> Vec<Vec<i32>> {
    let mut sub_sets = vec![];
    let number_of_combinations = 1 << original_set.len();

    for combination_index in 0..number_of_combinations {
        let mut sub_set = vec![];

        for set_element_index in 0..original_set.len() {
            if combination_index & (1 << set_element_index) != 0 {
                sub_set.push(original_set[set_element_index]);
            }
        }

        sub_sets.push(sub_set);
    }

    sub_sets
}

fn cascading_power_set(original_set: &[i32]) -> Vec<Vec<i32>> {
    let mut sets = vec![vec![]];

    for num_idx in 0..original_set.len() {
        let existing_sets_num = sets.len();

        for set_idx in 0..existing_sets_num {
            let mut set = sets[set_idx].clone();
            set.push(original_set[num_idx]);
            sets.push(set);
        }
    }

    sets
}

function backtrackingPowerSetRecursive(
  originalSet: number[],
  allSubsets: number[][] = [[]],
  currentSubSet: number[] = [],
  startAt: number = 0,
): number[][] {
  for (let position = startAt; position < originalSet.length; position += 1) {
    currentSubSet.push(originalSet[position]);
    allSubsets.push([...currentSubSet]);

    backtrackingPowerSetRecursive(
      originalSet,
      allSubsets,
      currentSubSet,
      position + 1,
    );

    currentSubSet.pop();
  }

  return allSubsets;
}

function bitwisePowerSet(originalSet: number[]): number[][] {
  const subSets: number[][] = [];
  const numberOfCombinations = 2 ** originalSet.length;

  for (
    let combinationIndex = 0;
    combinationIndex < numberOfCombinations;
    combinationIndex += 1
  ) {
    const subSet: number[] = [];

    for (
      let setElementIndex = 0;
      setElementIndex < originalSet.length;
      setElementIndex += 1
    ) {
      if (combinationIndex & (1 << setElementIndex)) {
        subSet.push(originalSet[setElementIndex]);
      }
    }

    subSets.push(subSet);
  }

  return subSets;
}

function cascadingPowerSet(originalSet: number[]): number[][] {
  const sets: number[][] = [[]];

  for (let numIdx = 0; numIdx < originalSet.length; numIdx += 1) {
    const existingSetsNum = sets.length;

    for (let setIdx = 0; setIdx < existingSetsNum; setIdx += 1) {
      const set = [...sets[setIdx], originalSet[numIdx]];
      sets.push(set);
    }
  }

  return sets;
}