# Problem Statement
We are given a set of integers and we have to find all the possible subsets of this set of integers. The following example elaborates on this further.

<br>

# Hint
* Guess the number of subsets for a set of size 'n'
* Combinations

<br>

# Try it yourself

void get_all_subsets(vector<int>& v, vector<unordered_set<int>>& sets) {	
    //TODO: Write - Your - Code
}

#include <string>
#include <vector>
#include <iostream>
#include <unordered_set>
#include <math.h>
using namespace std;


void print(vector<int>& v) {
  cout << "vector = {";
  for (int x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
void print_list(vector<T>& v) {
  cout << "{ ";
  for (auto x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
bool is_equal(vector<T>& v1, vector<T>& v2) {
  if (v1.size() != v2.size()) {
    return false;
  }

  int idx = 0;
  for (auto x : v1) {
    if (x != v2[idx]) {
      return false;
    }
    ++idx;
  }

  return true;
}

template<typename T>
vector<T> create_random_vector(int length, T max_value = 100) {
  vector<T> v(length);
  srand (time(nullptr));
  for(T i = 0; i < length; ++i) {
    v[i] = static_cast<T>(rand() % max_value);
  }
  return v;
}

vector<int> create_random_vector(int length, int max_value = 100) {
  vector<int> v(length);
  srand (time(nullptr));
  for(int i = 0; i < length; ++i) {
    v[i] = rand() % max_value;
  }
  return v;
}

int find_in_vector(vector<int>& v, int k) {
  for (int i = 0; i < v.size(); ++i) {
    if (k == v[i]) {
      return i;
    }
  }
  return -1;
}

bool is_sorted(vector<int> v) {

  for (int i = 1; i < v.size(); ++i) {
    if (v[i] < v[i-1]) {
      return false;
    }
  }

  return true;
}

class getSubsets{
  static void get_all_subsets(List<Integer> v, List<HashSet<Integer>> sets) {
	   //TODO: Write - Your - Code
  }
} 

Java

def get_all_subsets(v, sets):
  #TODO: Write - Your - Code
  return sets

Python

let get_all_subsets = function(v, sets) {
  //TODO: Write - Your - Code
};

JavaScript

def get_all_subsets(v, sets)
  #TODO: Write - Your - Code
 return sets
end

Ruby

int get_bit(int num, int bit) {
	int temp = (1 << bit);
	temp = temp & num;
	if (temp == 0) {
		return 0;
	}
	return 1;
}

void get_all_subsets(vector<int>& v, vector<unordered_set<int>>& sets) {	
	int subsets_count = pow((double)2, (double)v.size());
	for (int i = 0; i < subsets_count; ++i) {
		unordered_set<int> set;
		for (int j = 0; j < v.size(); ++j) {
			if (get_bit(i, j)) {
				set.insert(v[j]);
			}
		}
		sets.push_back(set);
	}
}

int main() {
  int myints[] = {8,13,3,22, 17, 39, 87, 45, 36};
	std::vector<int> v (myints, myints + sizeof(myints) / sizeof(int) );
	vector<unordered_set<int>> subsets;

	get_all_subsets(v, subsets);
	cout << "****Total*****" << subsets.size() << endl;
	for (int i = 0; i < subsets.size(); ++i) {
		cout << "{";
		for (unordered_set<int>::iterator it = subsets[i].begin(); it != subsets[i].end(); ++it) {
			cout << *it << ",";
		}
		cout << "}" << endl;
	}
	cout << "****Total***** = " << subsets.size() << endl;
	return 0;
}

class getSubsets{
  static int get_bit(int num, int bit) {
  	  int temp = (1 << bit);
	  temp = temp & num;
	  if (temp == 0) {
    	  return 0;
  	  }
	  return 1;
  }

  static void get_all_subsets(List<Integer> v, List<HashSet<Integer>> sets) {
	  int subsets_count = (int)(Math.pow((double)2, (double)v.size()));
	  for (int i = 0; i < subsets_count; ++i) {
    	  HashSet<Integer> set = new HashSet<Integer>();
    	  for (int j = 0; j < v.size(); ++j) {
      		  if (get_bit(i, j) == 1) {
        		  int x = v.get(j);
        		  set.add(x);
      		  }
    	  }
    	  sets.add(set);
	  }
  }
  public static void main(String[] args) {
    Integer[] myints = new Integer[] {8,13,3,22, 17, 39, 87, 45, 36};
    List<Integer> v = new ArrayList<Integer>();
    for (Integer i : myints) {
      v.add(i);
    }
    List<HashSet<Integer>> subsets = new ArrayList<HashSet<Integer>>();

    get_all_subsets(v, subsets);

    System.out.println("****Total*****" + subsets.size());
    for (int i = 0; i < subsets.size(); ++i) {
      System.out.print("{");
      for (Integer it : subsets.get(i)) {
        System.out.print(it + ", ");
      }
      System.out.println("}");
    }
    System.out.println("****Total*****" + subsets.size());
  }
}  

def get_bit(num, bit):
    temp = (1 << bit)
    temp = temp & num
    if temp == 0:
      return 0
    return 1
        
def get_all_subsets(v, sets):
    subsets_count = 2 ** len(v)
    for i in range(0, subsets_count):
      st = set([])
      for j in range(0, len(v)):
         if get_bit(i, j) == 1:
            st.add(v[j])
      sets.append(st)
      
def main():
    v = [8,13,3,22,17,39,87,45,36]
    subsets = []
    get_all_subsets(v, subsets);
    print("****Total*****" + str(len(subsets)))
    for i in range(0, len(subsets)):
        print("{", end = "")
        print(subsets[i], end = "")
        print("}")
    print("****Total*****" + str(len(subsets)))

main()      

def get_bit(num, bit)
  temp = (1 << bit)
  temp = temp & num
  if (temp == 0)
    return 0
  end

  return 1
end

def get_all_subsets(v, sets)
  subsets_count = 2**v.length
  for i in 0 .. subsets_count-1
    st = Set.new
    for j in 0 .. v.length-1
      if (get_bit(i, j) == 1)
        st.add(v[j])
      end
    end

    sets.push(st)
  end
end

def main()
  # v = [8,13,3,22, 17, 39, 87, 45, 36]
  v = [1,2,3]
  subsets = []
  get_all_subsets(v, subsets)
  print "****Total*****: #{subsets.length}\n"
  print "Subsets = #{subsets}\n"
end
main

# Solution Explanation
## Runtime Complexity
Exponential, $O(2^{n}* n)$ - where 'n' is number of integers in the given set.

## Memory Complexity
Exponential, $O(2^{n}* n)$

<br>

## Solution Breakdown

There are several ways to solve this problem. We will discuss the one that is neat and easier to understand. We know that for a set of 'n' elements there are $2^{n}$ subsets. For example, a set with 3 elements will have 8 subsets. Here is the algorithm we will use:

```html
n = size of given integer set
subsets_count = 2^n
for i = 0 to subsets_count
    form a subset using the value of 'i' as following:
        bits in number 'i' represent index of elements to choose from original set,
		if a specific bit is 1 choose that number from original set and add it to current subset,
        e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
    add current subset to list of all subsets
```
Note that the ordering of bits for picking integers from the set does not matter; picking integers from left to right would produce the same output as picking integers from right to left.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Find all subsets of a given set of integers.

Find All Subsets

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown