3.Cheerleaders(SotongPractice) Môtả ChomộtxâugồmNkítự(N≤10),yêucầuinratấtcảcáchoánvịphânbiệtcủaxâuđótheothứtựtừđiển. Vídụ Vớixâu“aba”,sẽcótấtcả3hoánvịkhácnhautheothứtựtừđiểnlà“aab”,“aba”,“baa”. Phântích MộtxâucóđộdàiNsẽcótốiđaN!hoánvịphânbiệtkhitấtcảcáckítựcủaxâuđóđềukhácnhau. Hướnggiải Vétcạn Dựavàotầnsốcủacáckítựtrongxâu,dùngkĩthuậtđệquyđểsinhratấtcảhoánvịkhácnhautheothứtựtừđiển. ĐộphứctạptínhtoánO(N!). 24 2. Exhaustive Search -Problem voidper(inti){ //basic condition// if(i == N){ cout << S << endl; return; } //Recursion// for (intj = 0; j < 26; j++){ if(cnt[j]){ S[i] = 'a'+j; cnt[j]--; per(i+1);//đệ quy cnt[j]++; } } }
package sinhhv;
import java.util.Scanner;
public class Solution { static int n; static char[] s = new char[20]; static char[] ans = new char[20]; static boolean[] vs = new boolean[20];
static void solve(int pos){
if(pos==n){
for(int i=0; i<n; i++){
System.out.print(ans[i]);
}
System.out.println();
return;
}
for(int i=0; i<n; i++){
if(vs[i]==true){
ans[pos] = s[i];
vs[i] = false;
solve(pos+1);
vs[i] = true;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
n = sc.nextInt();
String string = sc.next();
for(int i=0; i<string.length(); i++){
s[i] = string.charAt(i);
vs[i] = true;
}
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
if(s[j]<s[i]){
char t = s[j];
s[j] = s[i];
s[i] = t;
}
}
}
// for(int i=0; i<n; i++){ // System.out.print(s[i]); // } solve(0); } } }