  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Unique Power Set

Last Updated on May 17, 2022 by Ria Pathak Back Tracking

Medium

### Problem Statement :

Given `N` integers print all the distinct power sets of the sequence in lexicographical order.

See original problem statement here

### Solution Approach :

#### Introduction :

For every element we have exactly two choice, we can either include the element in the set or do not include the element in the set. We also have to keep track of the items which are currently picked up in our set so we do not use any element more than once.

#### Description:

We will use backtracking to solve the above problem.

Backtracking is the approach to solve the problem by testing all possible answers (by breaking the problems into subproblems). If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
Since it has duplicate items as well, we will keep track of the items already used, with the help of `used[]` array. If the current item has previously been used we skip that item, else we add it to `used[]` array. Now we will add items for every index of the array, breaking our problem into subproblems by recursively calling our function for the next index, every time we add elements from any index, we make sure to revert the changes back by deleting them to try another combinations (backtrack).

### Algorithm :

backtracking():

1. If `index > n`, return
2. print the subset.
3. else, for every `k= index` to `n-1` :
• if `k` is unused, add `k` to the used[] array
• add `arr[k]` to the subset.
• call backtrack(arr,k+1,n)
• remove `arr[k]` from the subset.

### Complexity Analysis :

Since we are making two choice for every element (either include it or don’t). Our recursion tree has 1 node (function calls) in `0th` level, 2 node(function calls) in `1st` level, 4 node (function calls) in `2nd` level and so on. Can you guess the final time complexity? or the number of nodes (function calls) in last level ?

### Solutions:

```#include <bits/stdc++.h>
using namespace std;

bool checkduplicate(vector<int> t, int n){
for(int i=0; i<t.size(); i++)
if(t[i] == n) return true;
return false;
}

void backtrack(vector<int>& A, vector<set<int> >& res,
vector<int>& subset, int index)
{
if(index>A.size())
return;

for(int i=0;i<subset.size();i++)
cout<<subset[i]<<" ";
cout<<endl;

vector<int> used;
for (int i = index; i < A.size(); i++)
{

if(checkduplicate(used, A[i]))
continue;

used.push_back(A[i]);

subset.push_back(A[i]);

backtrack(A, res, subset, i + 1);

subset.pop_back();
}

return;
}

void subsets(vector<int>& A)
{
vector<int> subset;

int index = 0;
backtrack(A, res, subset, index);
}

int main()
{
// find the subsets of below vector.
vector<int> array;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int c;
cin>>c;
array.push_back(c);
}

sort(array.begin(),array.end());
subsets(array);

// Print result

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int array[]=new int[n];
for(int i=0;i<n;i=i+1)
{
array[i]=sc.nextInt();
}
int set[]=new int[n];
int visited[]=new int;
for(int i=0;i<n;i=i+1)
{
visited[array[i]]=visited[array[i]]+1;
}
Arrays.sort(array);
recursion(array,visited,set,0,0);
}

static void recursion(int array[],int visited[],int set[],int position,int current)
{
if(current!=0)
print(set,current);

for(int i=position;i<array.length;i=i+1)
{
if(visited[array[i]]==0 )
{
continue;
}
if(i!=0 && array[i]==array[i-1])
continue;
set[current]=array[i];
visited[array[i]]-=1;
recursion(array,visited,set,i,current+1);
visited[array[i]]+=1;
}
}

static void print(int set[],int current)
{
for(int i=0;i<current;i=i+1)
{
System.out.print(set[i]+" ");
}
System.out.println();
}
}
```

[forminator_quiz id="2231"]

This article tried to discuss the concept of Back Tracking. Hope this blog helps you understand and solve the problem. To practice more problems on Back Tracking you can check out MYCODE | Competitive Programming.