Member Avatar for Ani_1
Ani_1 0 Newbie Poster

I'm working on an Anagram Finder program. One of the methods I'm writing introduces the concept of recursive backtracking which I'm completely new to. I'm hoping to get some suggestions of how this works/how to make it work.

I'm trying to implement recursive backtracking in order to display a list of words from a dictionary text file to form anagrams for an input phrase. Here's what I have so far:

public void printAnagrams(String phrase, int max, List<List<String>> anagrams) {
    if (anagrams == null) { 
        throw new IllegalArgumentException(); 
    } else if (max != 0) {
        System.out.println("...");
    } else 
        System.out.println("...");
    for (List<String> element : anagrams)
        System.out.println(anagrams);
}// End of printAnagram method

If max > 0, only combination of max words or less are displayed.
Since the program is pretty long, the background info is listed in the links below.

AnagramFinder class:

Client class:

This is the expected results:

File name? dict2.txt

Phrase to Scramble? off course

All words found in "off course":
[core, course, cs, cure, for, force, forces, four, of, off, offer, offers, or, our, ours, re, score, so, source, suffer, sure, us, use, user]

Max words to include (Enter for no max)? 3

[core, off, us]

[core, us, off]

[course, off]

[cure, off, so]

[cure, so, off]

[force, of, us]

[force, us, of]

[of, force, us]

[of, us, force]

[off, core, us]

[off, course]

[off, cure, so]

[off, so, cure]

[off, source]

[off, us, core]

[so, cure, off]

[so, off, cure]

[source, off]

[us, core, off]

[us, force, of]

[us, of, force]

[us, off, core]

  • 1 Contributor
  • 0 Replies
  • 314 Views

Dani AI

Generated

— Turn the phrase into a multiset of letters (int[26] counts is fast) and prefilter the dictionary to only words whose letter counts are subsets of the phrase. Backtracking then becomes: pick an unused candidate that fits the remaining counts, subtract its letters, recurse, restore the counts, and record a solution when no letters remain. Doing the cheap filtering and precomputing each word's counts up front reduces the search space a lot.

void backtrack(int[] rem, boolean[] used, List<String> cur) {
    if (isEmpty(rem)) {               // no letters left -> solution
        results.add(new ArrayList<>(cur));
        return;
    }
    if (max > 0 && cur.size() == max) return; // reached max words and still letters -> prune
    for (int i = 0; i < candidates.size(); i++) {
        if (used[i]) continue;
        int[] wc = wordCounts[i];       // precomputed counts for candidates[i]
        if (!canForm(rem, wc)) continue;
        used[i] = true;
        subtract(rem, wc);
        cur.add(candidates.get(i));
        backtrack(rem, used, cur);
        cur.remove(cur.size() - 1);
        add(rem, wc);
        used[i] = false;
    }
}

A few clarifications: the loop above iterates all unused words at each level, so it generates permutations (different orders of the same words). If you want combinations only (order-insensitive), iterate from a start index and pass i+1 into the recursive call. If the dictionary has duplicate strings, sort candidates and skip duplicates with the usual if (i>0 && words[i].equals(words[i-1]) && !used[i-1]) continue guard.

Practical tips: normalize input (lowercase, remove spaces/punctuation), precompute wordCounts, discard words longer than remaining letters, sort candidates (e.g., longer words first) for better pruning, and use max to limit search depth on large inputs. Test on tiny dictionaries first and add assertions for subtract/add so counts never go negative — that prevents subtle bugs.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.