Finding all the subsets of a set

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

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.

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

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.

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

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

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
    
    }

}

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

public static List<List> powerset(List array) { List<List> perms = new ArrayList<List>(); if(array.size()==0) { perms.add(new ArrayList()); 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;

}