{"id":2208,"date":"2020-06-14T16:07:02","date_gmt":"2020-06-14T16:07:02","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2208"},"modified":"2022-03-22T09:49:02","modified_gmt":"2022-03-22T09:49:02","slug":"possible-attack-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/possible-attack-2\/","title":{"rendered":"Possible Attack-2"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

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

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

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

Given N<\/code> integers print all distinct combinations.<\/p>\n<\/blockquote>\n

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

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to swap all the values one-by-one and keep track of the values used. In a set of n<\/code> elements with d<\/code> similar elements there are n!\/m!<\/code> different permutations. For example, there are 3<\/code> permutations of the set {1,1,2}, namely [1,1,2], [1,2,1], [2,1,1].<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description:<\/h4>\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 it has duplicate items as well, we will keep track of the items already used, with the help of used[]<\/code> array. Every time we see an unsed item we add it to used[]<\/code> array. Now we will swap every index of the array, breaking our problem into subproblems by recursively calling our function for the next index, when the index becomes equal to the size of the array we print the current combination, every time we swap indices we make sure to revert the changes by swapping them back again to try another combinations (backtrack).<\/p>\n<\/blockquote>\n

Algorithm :<\/h4>\n

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

    \n
  1. If index == n<\/code>, print the current combination.<\/li>\n
  2. 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
    • swap(index,k)<\/li>\n
    • call backtrack(arr,index+1,n)<\/li>\n
    • swap(index,k) , (Backtrack step).<\/li>\n<\/ul>\n<\/blockquote>\n<\/li>\n<\/ol>\n

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

      Total number of permutations are, as discussed earlier, n!<\/code>, and it takes O(n)<\/code> time to print each permutation. Can you guess the final time complexity<\/strong>?<\/p>\n<\/blockquote>\n

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