Finding all the subsets of a set

Question

I need an algorithm to find all of the subsets of a set where the number of elements in a set is n.

S={1,2,3,4...n}

Edit: I am having trouble understanding the answers provided so far. I would like to have step-by-step explanation of how the answers work to find the subsets.

For example,

S={1,2,3,4,5}

How do you know {1} and {1,2} are subsets?

Could someone help me with a simple function in c++ to find subsets of {1,2,3,4,5}

Mehala

The question is pretty vague, do you mean all possible subsets? – Dowry

The number of subsets isn't n! That is the number of permutations. The number of subsets (cardinality of the power set) is 2^n – Dowry

Answer 1

It's very simple to do this recursively. The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.

• For n=1, the set of subsets is {{}, {1}}
• For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.

Edit To make it crystal clear:

• The set of subsets of {1} is {{}, {1}}
• For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
• Repeat till you reach n

Leninist

THANKS BUT I STILL UNABLE TO FIGURE HOW COULD I ADD 2 TO EACH SUBSET AND HOW COULD I TAKE THE UNION...COULD U PLZ DESCRIBE WITH THIS SET {1,2,3,4,5} – Mehala

i mean if u tell me ur example in a algorithm or in a c/c++ program. – Mehala

The real base case should be "The powerset of {} is {{}}." Then the poserset of {n} is {{}} union {n}. And so forth. – Ashlynashman

True, but I thought it would be easier to understand this way. – Leninist

Your answer was so good..you pointed out the thing where I got stuck but if you could little more expand your idea just if you could provide the recursive function it will so much helpful. Again your answer still the best. – Porche

Anyone who is looking for code in javascript link – Renege

A late answer here: An elegant recursive solution that corresponds to the explanation above. The core vector operation is only 4 lines. credit to "Guide to Competitive Programming" book from Laaksonen, Antti. see the code in below answer https://mcmap.net/q/276918/-finding-all-the-subsets-of-a-set – Coulee

Answer 2

Too late to answer, but an iterative approach sounds easy here:

1) for a set of n elements, get the value of 2^n. There will be 2^n no.of subsets. (2^n because each element can be either present(1) or absent(0). So for n elements there will be 2^n subsets. ). Eg:
for 3 elements, say {a,b,c}, there will be 2^3=8 subsets

2) Get a binary representation of 2^n. Eg:
8 in binary is 1000

3) Go from 0 to (2^n - 1). In each iteration, for each 1 in the binary representation, form a subset with elements that correspond to the index of that 1 in the binary representation. Eg:

For the elements {a, b, c}
000 will give    {}
001 will give    {c}
010 will give    {b}
011 will give    {b, c}
100 will give    {a}
101 will give    {a, c}
110 will give    {a, b}
111 will give    {a, b, c}

4) Do a union of all the subsets thus found in step 3. Return. Eg:
Simple union of above sets!

Breeze

How will your solution handle n > 32 ? as I guess your saveing 2^n in an int.No? – Pinite

Sorry, I haven't written any code implementing the above, but yeah for n>32 using an int32 would be a problem :). An alternative solution is mentioned above by Michael Borgwardt. – Breeze

We can use a bit array of size n in place of an integer and use that instead if integer to iterate over all subsets.Can post my answer here if anyone is interested. – Hiltner

For any practical reason long will be more than enough. – Jackfish

Answer 3

In case anyone else comes by and was still wondering, here's a function using Michael's explanation in C++

vector< vector<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > subsetTemp = subset;  //making a copy of given 2-d vector.

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );   // adding set[i] element to each subset of subsetTemp. like adding {2}(in 2nd iteration  to {{},{1}} which gives {{2},{1,2}}.

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );  //now adding modified subsetTemp to original subset (before{{},{1}} , after{{},{1},{2},{1,2}}) 
    }
    return subset;
}

Take into account though, that this will return a set of size 2^N with ALL possible subsets, meaning there will possibly be duplicates. If you don't want this, I would suggest actually using a set instead of a vector(which I used to avoid iterators in the code).

Tabard

This is the best answer in my opinion. I converted this code to C# to understand it better, check it out here ideone.com/bnWlcM – Ferree

Ronald Rey's Answer was helpful. Full Source Code/ Implementaion Available Here in C++ – Quianaquibble

@AkshaySarkar Thank you! Glad I could help. – Tabard

Answer 4

If you want to enumerate all possible subsets have a look at this paper. They discuss different approaches such as lexicographical order, gray coding and the banker's sequence. They give an example implementation of the banker's sequence and discuss different characteristics of the solutions e.g. performance.

Dowry

Answer 5

Here, I've explained it in detail. Do upvote, if you like the blogpost.

http://cod3rutopia.blogspot.in/

Any way if you can't find my blog here is the explanation.

Its a problem which is recursive in nature.

Essentially for an element to be present in a subset there are 2 options:

1)It is present in the set

2)It is absent in the set.

This is the reason why a set of n numbers has 2^n subsets.(2 options per element)

Here is the pseudo-code(C++) to print all the subsets followed by an example explaining how the code works. 1)A[] is the array of numbers whose subsets you want to find out. 2) bool a[] is the array of booleans where a[i] tells whether the number A[i] is present in the set or not.

print(int A[],int low,int high)  
   {
    if(low>high)  
    {
     for(all entries i in bool a[] which are true)  
        print(A[i])
    }  
   else  
   {set a[low] to true //include the element in the subset  
    print(A,low+1,high)  
    set a[low] to false//not including the element in the subset  
    print(A,low+1,high)
   }  
  }  

Draconian

What if the blog is not online anymore? Or just down for maintenance? Provide the source code IN your answer, dont link to it. – Cooking

OK Manuel but the problem is I don't want to merely provide the source code .I've an explanation along with it and I don't want to write everything all over again. – Draconian

If there is already everything explained in your blogpost, just copy+paste it? – Cooking

I've made the changes. – Draconian

Answer 6

Bottom up with O(n) space solution

#include <stdio.h>

void print_all_subset(int *A, int len, int *B, int len2, int index)
{
    if (index >= len)
    {
        for (int i = 0; i < len2; ++i)
        {
            printf("%d ", B[i]);
        }
        printf("\n");

        return;
    }
    print_all_subset(A, len, B, len2, index+1);

    B[len2] = A[index];
    print_all_subset(A, len, B, len2+1, index+1);
}



int main()
{
    int A[] = {1, 2, 3, 4, 5, 6, 7};
    int B[7] = {0};

    print_all_subset(A, 7, B, 0, 0);
}

Marengo

Answer 7

Here is a simple recursive algorithm in python for finding all subsets of a set:

def find_subsets(so_far, rest):
        print 'parameters', so_far, rest
        if not rest:
            print so_far
        else:
            find_subsets(so_far + [rest[0]], rest[1:])
            find_subsets(so_far, rest[1:])


find_subsets([], [1,2,3])

The output will be the following: $python subsets.py

parameters [] [1, 2, 3]
parameters [1] [2, 3]
parameters [1, 2] [3]
parameters [1, 2, 3] []
[1, 2, 3]
parameters [1, 2] []
[1, 2]
parameters [1] [3]
parameters [1, 3] []
[1, 3]
parameters [1] []
[1]
parameters [] [2, 3]
parameters [2] [3]
parameters [2, 3] []
[2, 3]
parameters [2] []
[2]
parameters [] [3]
parameters [3] []
[3]
parameters [] []
[]

Watch the following video from Stanford for a nice explanation of this algorithm:

https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9

Blastopore

Answer 8

Here is an implementation of Michael's solution for any type of element in std::vector.

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

// Find all subsets
template<typename element>
vector< vector<element> > subsets(const vector<element>& set)
{
  // Output
  vector< vector<element> > ss;
  // If empty set, return set containing empty set
  if (set.empty()) {
    ss.push_back(set);
    return ss;
  }

  // If only one element, return itself and empty set
  if (set.size() == 1) {
    vector<element> empty;
    ss.push_back(empty);
    ss.push_back(set);
    return ss;
  }

  // Otherwise, get all but last element
  vector<element> allbutlast;
  for (unsigned int i=0;i<(set.size()-1);i++) {
    allbutlast.push_back( set[i] );
  }
  // Get subsets of set formed by excluding the last element of the input set
  vector< vector<element> > ssallbutlast = subsets(allbutlast);
  // First add these sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }
  // Now add to each set in ssallbutlast the last element of the input
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ssallbutlast[i].push_back( set[set.size()-1] );
  }
  // Add these new sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }

  return ss;

}

// Test
int main()
{

  vector<char> a;
  a.push_back('a');
  a.push_back('b');
  a.push_back('c');


  vector< vector<char> > sa = subsets(a);

  for (unsigned int i=0;i<sa.size();i++) {
    for (unsigned int j=0;j<sa[i].size();j++) {
      cout << sa[i][j];
    }
    cout << endl;
  }

  return 0;

}

Output:

(empty line)
a
b
ab
c
ac
bc
abc

Negativism

Answer 9

An elegant recursive solution that corresponds to the best answer explanation above. The core vector operation is only 4 lines. credit to "Guide to Competitive Programming" book from Laaksonen, Antti.

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

vector<int> subset;
void search(int k, int n) {
    if (k == n+1) {
    // process subset - put any of your own application logic
    // for (auto i : subset) cout<< i << " ";
    // cout << endl;
    }
    else {
        // include k in the subset
        subset.push_back(k);
        search(k+1, n);
        subset.pop_back();
        // don't include k in the subset
        search(k+1,n);
    }
}

int main() {
    // find all subset between [1,3]
    search(1, 3);
}

Coulee

Answer 10

You dont have to mess with recursion and other complex algorithms. You can find all subsets using bit patterns (decimal to binary) of all numbers between 0 and 2^(N-1). Here N is cardinality or number-of-items in that set. The technique is explained here with an implementation and demo.

http://codeding.com/?article=12

Crescentia

Answer 11

Here is a solution in Scala:

def subsets[T](s : Set[T]) : Set[Set[T]] = 
  if (s.size == 0) Set(Set()) else { 
    val tailSubsets = subsets(s.tail); 
    tailSubsets ++ tailSubsets.map(_ + s.head) 
} 

Mayence

Answer 12

Here's some pseudocode. You can cut same recursive calls by storing the values for each call as you go and before recursive call checking if the call value is already present.

The following algorithm will have all the subsets excluding the empty set.

list * subsets(string s, list * v){
    if(s.length() == 1){
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);     
        int length = temp->size();

        for(int i=0;i<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

Karalynn

Answer 13

Here is a working code which I wrote some time ago

// Return all subsets of a given set
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<cstring>
#include<climits>
#include<cmath>
#include<iterator>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;


typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< vector<int> > vvi;
typedef vector<string> vs;

vvi get_subsets(vi v, int size)
{
    if(size==0) return vvi(1);
    vvi subsets = get_subsets(v,size-1);

    vvi more_subsets(subsets);

    for(typeof(more_subsets.begin()) it = more_subsets.begin(); it !=more_subsets.end(); it++)
    {
        (*it).push_back(v[size-1]);
    }

    subsets.insert(subsets.end(), (more_subsets).begin(), (more_subsets).end());
    return subsets;
}

int main()
{
    int ar[] = {1,2,3};
    vi v(ar , ar+int(sizeof(ar)/sizeof(ar[0])));
    vvi subsets = get_subsets(v,int((v).size()));


    for(typeof(subsets.begin()) it = subsets.begin(); it !=subsets.end(); it++)
    {
        printf("{ ");

        for(typeof((*it).begin()) it2 = (*it).begin(); it2 !=(*it).end(); it2++)
        {
            printf("%d,",*it2 );
        }
        printf(" }\n");
    }
    printf("Total subsets = %d\n",int((subsets).size()) );
}

Strap

@BenVoigt, sorry for that, now I have edited the code ,removed the macros, so that it is easily understood – Strap

@Strap could you help me on #49453104 – Moyra

Answer 14

This question is old. But there's a simple elegant recursive solution to OP's problem.

using namespace std;
void recsub(string sofar, string rest){
  if(rest=="") cout<<sofar<<endl;
  else{
    recsub(sofar+rest[0], rest.substr(1)); //including first letter
    recsub(sofar, rest.substr(1)); //recursion without including first letter.
  }
}
void listsub(string str){
  recsub("",str);
}
int main(){
  listsub("abc");
  return 0;
}

//output
abc
ab
ac
a
bc
b
c

//end: there's a blank output too representing empty subset

Hellen

Answer 15

one simple way would be the following pseudo code:

Set getSubsets(Set theSet)
{
  SetOfSets resultSet = theSet, tempSet;


  for (int iteration=1; iteration < theSet.length(); iteration++)
    foreach element in resultSet
    {
      foreach other in resultSet
        if (element != other && !isSubset(element, other) && other.length() >= iteration)
          tempSet.append(union(element, other));
    }
    union(tempSet, resultSet)
    tempSet.clear()
  }

}

Well I'm not totaly sure this is right, but it looks ok.

Baroque

Answer 16

here is my recursive solution.

vector<vector<int> > getSubsets(vector<int> a){


//base case
    //if there is just one item then its subsets are that item and empty item
    //for example all subsets of {1} are {1}, {}

    if(a.size() == 1){
        vector<vector<int> > temp;
        temp.push_back(a);

        vector<int> b;
        temp.push_back(b);

        return temp;

    }
    else
    {


         //here is what i am doing

         // getSubsets({1, 2, 3})
         //without = getSubsets({1, 2})
         //without = {1}, {2}, {}, {1, 2}

         //with = {1, 3}, {2, 3}, {3}, {1, 2, 3}

         //total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}}

         //return total

        int last = a[a.size() - 1];

        a.pop_back();

        vector<vector<int> > without = getSubsets(a);

        vector<vector<int> > with = without;

        for(int i=0;i<without.size();i++){

            with[i].push_back(last);

        }

        vector<vector<int> > total;

        for(int j=0;j<without.size();j++){
            total.push_back(without[j]);
        }

        for(int k=0;k<with.size();k++){
            total.push_back(with[k]);
        }


        return total;
    }


}

Karalynn

Answer 17

a simple bitmasking can do the trick as discussed earlier .... by rgamber

#include<iostream>
#include<cstdio>

#define pf printf
#define sf scanf

using namespace std;

void solve(){

            int t; char arr[99];
            cin >> t;
            int n = t;
            while( t-- )
            {
                for(int l=0; l<n; l++) cin >> arr[l];
                for(int i=0; i<(1<<n); i++)
                {
                    for(int j=0; j<n; j++)
                        if(i & (1 << j))
                        pf("%c", arr[j]);
                    pf("\n");
                }
            }
        }

int main() {
      solve();
      return 0;
}

Stackhouse

Answer 18

For those who wants a Simple implementation using std::vector and std::set for the Michael Borgwardt's algorithm:

// Returns the subsets of given set
vector<set<int> > subsets(set<int> s) {
    vector<set<int> > s1, s2;
    set<int> empty;
    s1.push_back(empty); // insert empty set
    // iterate over each element in the given set
    for(set<int>::iterator it=s.begin(); it!=s.end(); ++it) {
        s2.clear(); // clear all sets in s2
        // create subsets with element (*it)
        for(vector<set<int> >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) {
            set<int> temp = *s1iter;
            temp.insert(temp.end(), *it);
            s2.push_back(temp);
        }
        // update s1 with new sets including current *it element
        s1.insert(s1.end(), s2.begin(), s2.end());
    }
    // return
    return s1;
}

Goosefish

Answer 19

 vector<vetor<int>> subarrays(vector<int>& A) {
        vector<vetor<int>> set;
        vector<vector<int>> tmp;
        
        set.push_back({});
        set.push_back({});
        set[1].push_back(A[0]);
        
        for(int i=1;i<A.size();i++){
            tmp=set;
            for(int j=0;j<tmp.size();j++){
                tmp[j].push_back(A[i]);
            }
            set.insert( set.end(), tmp.begin(), tmp.end() );
        }
        return set;
    }

Lapidate

Answer 20

Here is the code as per original answer

    void print_subsets(std::vector<int>& nums, int i, std::vector<std::vector<int>>& results, std::vector<int>& r) {    
        if (i < nums.size()) {    
            r.push_back(nums[i]);  // First consider the element
            print_subsets(nums, i + 1, results, r);
            r.pop_back(); // Now don't consider the element
            print_subsets(nums, i + 1, results, r);
        }
        else {
            results.push_back(r);
        }     
    }

// Main method
   vector<vector<int>> subsets(vector<int>& nums) {
        std::vector<std::vector<int>> results;
        std::vector<int> r;
        print_subsets(nums, 0, results, r);        
        return results;
    }

Confidante

Answer 21

The recursive solution in Swift, as per the accepted:

private func getSubsets(_ set: Set<Int>) -> Set<Set<Int>> {

    var set = set // Allows you to manipulate the set

    if set.isEmpty { // Base Case: Subset of an empty set is an empty set
    
        return [[]]
    
    } else { // Remove n, find subset of 1,...,n - 1, duplicate subset and append n to duplicated set, return the union of both
    
        let n = set.removeFirst()
    
        var subset = getSubsets(set)
    
        for i in subset {
            var temp = i
            temp.insert(n)
            subset.insert(temp)
        }
    
        return subset
    
    }

}

Tartrate

Answer 22

Java Version without recursion based on "Michael Borgwardt" algo above.

public static List<List<Integer>> powerset(List<Integer> array) {
    List<List<Integer>> perms = new ArrayList<List<Integer>>();
    if(array.size()==0) {
        perms.add(new ArrayList<Integer>());
        return perms;
    }
return powerset(array, perms);
}

public static List<List<Integer>> powerset(List<Integer> array, List<List<Integer>> perms) {
    
    for(int i=0;i<array.size();i++){
        perms.add(Arrays.asList(array.get(i)));
        int x=perms.size();
        for(int j=0;j<x;j++){
            List<Integer> tmp = new ArrayList<Integer>(perms.get(j));   
            if(!(tmp.size()==1 && tmp.get(0)==array.get(i))){
                tmp.add(array.get(i));
                perms.add(tmp);
            }
        }
    }
    perms.add(new ArrayList<Integer>());
return perms;

}

Wain