Tricky Permutations

#1

My code works but time limit exceeded for last test case.
What can be more efficient way to solve this?
import java.util.*;
public class Main {

	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	String input = sc.next();
	char[] arg = input.toCharArray();
	Arrays.sort(arg);
	ArrayList<String> answer = new ArrayList<String>();
	
	trickyPermutations(arg,"",new boolean[input.length()],answer );
	for(String a : answer) {
		System.out.println(a);
	}

}



public static void trickyPermutations(char[] arr, String ans, boolean[] visited, ArrayList<String> answer) {
	if(ans.length()==arr.length) {
		if(!answer.contains(ans))
			answer.add(ans);
		return;
	}
	
	
	for(int i = 0; i < arr.length; i++) {
		if(!visited[i]) {
		visited[i] = true;
		trickyPermutations(arr,ans+arr[i],visited,answer);
		visited[i] = false;
	}
		
	}
	

	
}

}

#2

https://ide.codingblocks.com/s/651226 code link

#3

Hey @srishti200201_c9588863a697e1e7 You can solve this question by recursion:
To Solve any Problem related to Recursion All you need to do is Break the Problem into 3 important components which are as follows :-

  1. Bigger Problem : The original Problem statement is your bigger problem.
  2. Smaller Problem : In every recursive prblm there exist a prblm statement which you need to achieve in order to fullfill the prblm statement but by considering such a smaller prblm from the bigger prblm is needed which we need to assume that the recursion will work and will give the answer.
  3. Self Work : The amount of work which one should do in order to make the smaller problem your problem.

For e.g…, In order to find the max of any array, three components will be :-
Bigger Problem : To find the max in whole array viz find max in array from index 0 to n - 1.
Smaller Problem : Assume that the recursion works and will find the max of array from index 1 to n - 1.
Self Work : In order to make your smaller prblm your bigger prblm all you need to do is to compare the ans return by assuming the smaller prblm works with the 0th index element and return the max among both of them.

Similarly Classification acc to the Given prblm :-

  • Bigger Problem : To Print all of the possible permutations.
  • Smaller Problem : Assume the recursion works and will give you ans for permutations of String except first character.
    Self Work : In order to make you smaller prblm your problem all you need to work for the 0th index element. Because it could be the part included in the answer or not. So, the 0th element will be added to every possible position.

For e.g… ABC suppose the ans for BC can be available by recursion viz, BC and CB your work is the place A at every possible position in BC and CB. like, BC and B C and BC_ where the _ shows the possible position where A must be added.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

Sir i have followed a similar approach but i need to optimise the code due to time limit exceeded error…how can i optimize the code??

#6

Hey @srishti200201_c9588863a697e1e7 You are taking ArrayList to store all the answers and to put Answers in array list it takes time. So instead of using recursionGET approach use recursionPRINT approach.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.