LearnFrenzy
Sign in Take a free test

Methods and Recursion · Methods and Recursion Programs · Question 2

All permutations of a string with recursion in Java Solution, output & explanation

  • Program
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 2 Back to Exercise

Print all permutations of a string with distinct characters using recursion (choose each character as the first, permute the rest), and count them.

Solution
Main.java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static void permute(String prefix, String rest, List<String> out) {
        if (rest.isEmpty()) {
            out.add(prefix);
            return;
        }
        for (int i = 0; i < rest.length(); i++) {
            permute(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1), out);
        }
    }

    public static void main(String[] args) {
        List<String> perms = new ArrayList<>();
        permute("", "abc", perms);
        System.out.println(perms + " " + perms.size());
        perms.clear();
        permute("", "java".replace("a", "").concat("A"), perms);   // "jvA": 3 distinct letters
        System.out.println(perms.size());
    }
}

Output Verified by compiling and running

[abc, acb, bac, bca, cab, cba] 6
6

For n distinct characters there are n! permutations; each level of recursion fixes one more position.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links