Tutorialspoint.dev

Backtracking to find all subsets

Given a set of positive integers, find all its subsets.
Examples:

Input : 1 2 3
Output :     // this space denotes null element. 
         1
         1 2
         1 2 3
         1 3
         2
         2 3
         3

Input : 1 2
Output : 
         1 
         2
         1 2


We have already discussed iterative approach to find all subsets. This article aims to provide a backtracking approach.

Idea is that if we have n number of elements inside an array, we have exactly two choices for each of the elements. Either we include that element in our subset or we do not include it.

// CPP program to find all subsets by backtracking.
#include <bits/stdc++.h>
using namespace std;
  
// In the array A at every step we have two
// choices for each element either  we can
// ignore the element or we can include the
// element in our subset
void subsetsUtil(vector<int>& A, vector<vector<int> >& res,
                 vector<int>& subset, int index)
{
    for (int i = index; i < A.size(); i++) {
  
        // include the A[i] in subset.
        subset.push_back(A[i]);
        res.push_back(subset);
  
        // move onto the next element.
        subsetsUtil(A, res, subset, i + 1);
  
        // exclude the A[i] from subset and triggers
        // backtracking.
        subset.pop_back();
    }
  
    return;
}
  
// below function returns the subsets of vector A.
vector<vector<int> > subsets(vector<int>& A)
{
    vector<int> subset;
    vector<vector<int> > res;
  
    // include the null element in the set.
    res.push_back(subset);
  
    // keeps track of current element in vector A;
    int index = 0;
    subsetsUtil(A, res, subset, index);
  
    return res;
}
  
// Driver Code.
int main()
{
    // find the subsets of below vector.
    vector<int> array = { 1, 2, 3 };
  
    // res will store all subsets.
    // O(2 ^ (number of elements inside array))
    // because at every step we have two choices
    // either include or ignore.
    vector<vector<int> > res = subsets(array);
  
    // Print result
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
  
    return 0;
}

Output:

1 
1 2 
1 2 3 
1 3 
2 
2 3 
3 

Time Complexity : O(2 ^ n)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter