Approach
The idea is to generate all the permutations using recursion and backtracking and checking each of them whether it satisfies the given constraint or not.
Steps To Solve
 Initialize a hashmap 'mp' to avoid duplicates.
 Declare a variable 'ans' to store the count.

Make a function bool check(string &s) to check whether the number formed by the string s is valid or not.
 If the size of s is zero, return false.
 Convert string s to integer using the inbuilt stoi function and store the integer in num.
 If mp[num] == 1, it is already processed, return false. Else mark mp[num] as true.
 If num == 1, it is not a prime number, return false.
 If num == 2, it is a prime, return true.
 If num%2 == 0, it is not a prime, return false.
 As 2 is only the even prime, and we have already checked for that, iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not, if yes return false.
 If num passes all the above conditions, then it is a prime number that is not yet processed, so return true.

Make a function void solve(string &s, string &curr, vector <bool> &vis, int &N) to generate all possible permutations.
 Check whether the current string 'curr' is valid or not by calling check(curr). If it returns true, increment the answer by 1.
 Iterate over a range [0, N], using the variable i, and perform the following steps 
 Check whether the ith character of string s is included in the current string curr or not (vis[i] == true or false).
 If vis[i] == false, mark it as true and push s[i] into curr.
 Recursively call the function solve(s, curr, vis, N).
 Backtrack to generate all the possible strings.
 Call the function solve by passing the parameters (s, curr, vis, N).
 Print the answer.
Code
#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 7;
//hashmap avoid duplicates
unordered_map <int, int> mp;
//to store the answer
int ans;
//function to check whether the number formed by the string s is valid or not.
bool check(string &s){
//If the size of s is zero
if(s.size() == 0)
return false;
//Convert string s to integer
int num = stoi(s);
if(mp[num])
//already processed
return false;
//mark num as processed
mp[num] = true;
//1 is not a prime
if(num == 1)
return false;
//2 is a prime number
if(num == 2)
return true;
//2 is a factor
if(num%2 == 0)
return false;
//iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not
for(int i = 3; i * i <= num; i += 2){
if(num%i == 0)
return false;
}
//num is a prime number
return true;
}
// function to generate all possible permutations
void solve(string &s, string &curr, vector <bool> &vis, int &N){
//check current string
if(check(curr)){
//increment answer by 1
++ans;
}
for(int i = 0; i < N; ++i){
//Check whether the ith character of string s is included in the current string curr or not
if(vis[i])
continue;
//mark i visited
vis[i] = true;
//puch character s[i] to curr
curr.push_back(s[i]);
solve(s, curr, vis, N);
//backtrack
curr.pop_back();
vis[i] = false;
}
}
signed main(){
string s;
cin >> s;
int N = s.size();
vector <bool> vis(N, 0);
string curr = "";
//function call
solve(s, curr, vis, N);
//print the answer
cout << ans << "\n";
return 0;
}
Input
12345
Output
36
Complexities
Time Complexity
The time complexity is O(9^N)
Space Complexity
The space complexity is O(N) (ignoring the stack frames).
FAQs

What is Backtracking?
Backtracking is an algorithmic tool that recursively generates all the possible combinations to solve the given problem.

How do you check if a number is prime or not efficiently?
Checkout this coding ninjaâ€™s blog to get a better understanding.
Key Takeaways
In this article, we solved a problem using recursion and backtracking. If you want to master competitive programming or prepare for coding interviews, then backtracking is one of the most important topics. Check out this coding ninjas' blog for getting a better hold on it.
Also read, Permutation of string
To learn more about such data structures and algorithms, Coding Ninjas Studio is a onestop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various productbased companies by providing Online Mock Test Series and many more benefits.
Happy learning!