{"id":2229,"date":"2020-06-14T18:23:58","date_gmt":"2020-06-14T18:23:58","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2229"},"modified":"2022-05-17T06:53:25","modified_gmt":"2022-05-17T06:53:25","slug":"unique-power-set","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/unique-power-set\/","title":{"rendered":"Unique Power Set"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given N<\/code> integers print all the distinct power sets of the sequence in lexicographical order.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

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.<\/p>\n<\/blockquote>\n

Description:<\/h4>\n
\n

We will use backtracking to solve the above problem.<\/p>\n

Backtracking<\/strong> 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.
\nSince it has duplicate items as well, we will keep track of the items already used, with the help of used[]<\/code> array. If the current item has previously been used we skip that item, else we add it to used[]<\/code> 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).<\/p>\n<\/blockquote>\n

Algorithm :<\/h3>\n

backtracking()<\/strong>:<\/p>\n

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

      Complexity Analysis :<\/h3>\n
      \n

      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<\/code> level, 2 node(function calls) in 1st<\/code> level, 4 node (function calls) in 2nd<\/code> level and so on. Can you guess the final time complexity<\/strong>? or the number of nodes (function calls) in last level ?<\/p>\n<\/blockquote>\n

      Solutions:<\/h3>\n\t\t\t\t\t\t