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 according to data structures and algorithms.
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();
    }
  }
Previous post Possible Numbers
Next post Tug of War

Leave a Reply

Your email address will not be published. Required fields are marked *