(UVA) DNA - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=3112

The solution below used Backtracking to solve this problem. Every time that the method rec is called, it will keep the character in the current position (numChanges+0) or it will change the character by a character in the array elements (numChanges+1).


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

class Main {
    public int length;
    public int numAllowedChanges;
    public String sequence;
    public char[] dna;
    public char[] elements = {'A', 'C', 'G', 'T'};
    public TreeSet<String> mutatedDNA;
  
    public void rec(char[] dnaArray, int index, int numChanges) {
        if (numChanges > numAllowedChanges) {
            return;
        }
        if (index == length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < dnaArray.length; i++) {
                sb.append(dnaArray[i]);
            }
            mutatedDNA.add(sb.toString());
            return;
        }
      
        for (int j = 0; j < 4; j++) { // try every character in elements for this position
            char tmp = dnaArray[index];
            dnaArray[index] = elements[j];
            rec(dnaArray, index+1, numChanges+(elements[j] == tmp ? 0 : 1));
            dnaArray[index] = tmp;
        }
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            length = sc.nextInt();
            numAllowedChanges = sc.nextInt();
            sequence = sc.next();
            dna = new char[sequence.length()];
            for (int i = 0; i < sequence.length(); i++) {
                dna[i] = sequence.charAt(i);
            }
          
            mutatedDNA = new TreeSet<>();
            rec(dna, 0, 0);
          
            bw.write(mutatedDNA.size()+"\n");
            for (String s : mutatedDNA) {
                bw.write(s+"\n");
            }
        }
                                             
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}