CodingGyan

Generate All Subsets

medium Recursion and Backtracking

Problem

Read a word with different letters (up to 6 letters). Print all subsets of its letters (the letters keep their original order), one per line. Print them in this order: a subset first, then all subsets that extend it. The empty subset is printed as empty. Example for abc: empty, a, ab, abc, ac, b, bc, c.

Constraints

  • 1 <= length <= 6, different letters

Examples

Input

abc

Output

empty
a
ab
abc
ac
b
bc
c

Solutions

Best approachTime O(n * 2^n)Space O(n)

For n letters there are 2^n subsets. We build them depth-first: record the current subset, then try to add each later letter, and remove it again.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Print all subsets.
 * Input   : One word.
 * Output  : All subsets.
 * Approach: Include or skip each letter.
 * Time    : O(n * 2^n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // This method adds the current subset to the result. Then it extends the subset with each later letter.
        static void build(String s, int start, StringBuilder current, java.util.List<String> result) {
            // Step 1: Every state of "current" is a valid subset. An empty subset is printed as "empty".
            result.add(current.length() == 0 ? "empty" : current.toString());

            // Step 2: Add one more letter. Only letters after "start" are allowed, so no subset appears twice.
            for (int i = start; i < s.length(); i++) {
                current.append(s.charAt(i));
                build(s, i + 1, current, result);

                // Step 3: Remove the letter again (backtracking).
                current.deleteCharAt(current.length() - 1);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        java.util.List<String> result = new java.util.ArrayList<>();
        build(s, 0, new StringBuilder(), result);
        return result.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}
Hints (1)
  1. How many subsets does a word with 3 letters have?

Try these next