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}

Answer 1

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;

}

Answer 2

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;
}

Answer 3

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

Answer 4

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
    
    }

}

Answer 5

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;
    }

Answer 6

 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;
    }

Answer 7

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).

Answer 8

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!

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);
}

Answer 10

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

Answer 11

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;
}

Answer 12

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

Answer 13

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);
}

Answer 14

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()) );
}

Answer 15

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;
    }


}

Answer 16

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)
   }  
  }  

Answer 17

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;
    }
}

Answer 18

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) 
} 

Answer 19

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

Answer 20

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.

Answer 21

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

Answer 22

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.