# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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 >& 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 > subsets(vector<``int``>& A) ` `{ ` `    ``vector<``int``> subset; ` `    ``vector > 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 > 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)