{"id":2221,"date":"2020-06-14T17:20:16","date_gmt":"2020-06-14T17:20:16","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2221"},"modified":"2022-05-17T06:56:29","modified_gmt":"2022-05-17T06:56:29","slug":"possible-numbers","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/possible-numbers\/","title":{"rendered":"Possible Numbers"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

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

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

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

Given a string, we have to find total number of different sequences that can be formed using the letters in the string.<\/p>\n<\/blockquote>\n

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

Introduction :<\/h3>\n
\n

We will first generate all the subsets. 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. After generating all the subsets we will calcute number of permutations for each subset and add all of them to get our final answer.<\/p>\n<\/blockquote>\n

Description:<\/h3>\n
\n

We will use backtracking to solve the above problem.
\nBacktracking<\/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 our set 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). Now after we generate all distint subsets, we will calculate the total permutations for each subset and add the permutations of all the subsets to get the final answer. As the set contains duplicate values our subset will contain duplicate values as well so we will use the formula n!\/m!<\/code>, where n<\/code> is the size of subset and m<\/code> is the repeated items (characters) in the set.
\nFor example, our set is {a,a,b} then the total permutations will be 3!\/2! = 3<\/code>, where n=3<\/code> & m=2<\/code>.<\/p>\n<\/blockquote>\n

Algorithm :<\/h3>\n

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

    \n
  1. If index > n<\/code>, return<\/li>\n
  2. calculate the permutation and add it to result<\/code> .<\/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
    • print the result<\/code>.<\/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, 5 node (function calls) in 2nd<\/code> level and so on. Calculating factorial of set size m<\/code> can be done in O(n)<\/code>. 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