Unique Power Set

Last Updated on May 17, 2022 by Ria Pathak

Concepts Used

Back Tracking

Difficulty Level

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 {
    //static ArrayList<Integer>answer=new ArrayList<>();
    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[1000];
      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.