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.

Backtrackingis 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():**

- If
`index > n`

, return - calculate the permutation and add it to
`result`

. - 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.

- if
- 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 finaltime 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.