Possible Numbers

Last Updated on May 17, 2022 by Ria Pathak

Concepts Used

Back Tracking

Difficulty Level

Easy

Problem Statement :

Given a string, we have to find total number of different sequences that can be formed using the letters in the string.

See original problem statement here

Introduction :

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.

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 our set 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). 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!, where n is the size of subset and m is the repeated items (characters) in the set.
For example, our set is {a,a,b} then the total permutations will be 3!/2! = 3, where n=3 & m=2.

Algorithm :

backtracking():

1. If index > n, return
2. calculate the permutation and add it to result .
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.

4. print the result.

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, 5 node (function calls) in 2nd level and so on. Calculating factorial of set size m can be done in O(n). 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; 
      int countt = 0;

      unsigned int factorial(unsigned int n) 
      { 
        if (n == 0) 
            return 1; 
        return n * factorial(n - 1); 
      } 


      bool checkduplicate(vector<char> t, char n){
                  for(int i=0; i<t.size(); i++)
                      if(t[i] == n) return true;
                  return false;
              }


      void backtrack(vector<char>& A, vector<char>& subset,int index) 
      { 
          if(index>A.size())
           return;

          vector<char> vis;
          int rep=1;
            for(int i=0;i<subset.size();i++)
            {

               if(checkduplicate(vis,subset[i]))
               {
                 rep++;
               }
            }
        if(vis.size())
          countt += factorial(subset.size())/factorial(rep);



        vector<char> 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, subset, i + 1); 


              subset.pop_back(); 
          } 

          return; 
      } 

      vector<set<int> > subsets(vector<char>& A) 
      { 
          vector<char> subset; 
          vector<set<int> > res; 

          int index = 0; 
          backtrack(A, subset, index); 

          return res; 
      } 


      int main() 
      { 
          vector<char> array;
          string str;
          cin>>str;
          int n = str.length();
          for(int i=0;i<n;i++)
          {
            array.push_back(str[i]);
          }
        subsets(array); 
        cout<<countt;
          return 0; 
      } 

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    //write your code here
    Scanner input = new Scanner(System.in);
    String S;
    S = input.next();
    System.out.println(solve(S));
  }

   public static int solve(String S) {
        int[] count = new int[26];
        for (char c : S.toCharArray()) count[c - 'A']++;
        return dfs(count);
    }

   static int dfs(int[] arr) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0) continue;
            sum++;
            arr[i]--;
            sum += dfs(arr);
            arr[i]++;
        }
        return sum;
    }
}

[forminator_quiz id="2223"]

This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.