Generation of all subsets of strings for a given string

Question

I want a code to generate all the subsets of strings of the given string.

I tried this on my own and came up with this :

 public static void main(String[] args){
    long startTime = System.nanoTime(); 
    String text = "1234";
    int n = text.length();
    String k = "";
    for(int i=0;i < Math.pow(2, n);i++){
        k = Integer.toBinaryString(i);
        while(k.length() != n){
            k = "0"+k;
        }
        StringBuilder sb = new StringBuilder();
        for(int j=0;j<k.length();j++){
            if(k.charAt(j) == '1'){
                sb.append(text.charAt(j));
            }
        }
    //  System.out.println(String.format("%04d",
    //      Integer.parseInt(k)));
        System.out.println(sb.toString());
    }
    long endTime = System.nanoTime();
    long duration = endTime - startTime;
    System.out.println("Duration:" + duration);
}

But this is a horrible O(n^2) algorithm so I was looking for a better solution and found this:

public static void comb2(String s) { 
    comb2("", s);
}
private static void comb2(String prefix, String s) {
    System.out.println(prefix);
    for (int i = 0; i < s.length(); i++){
        comb2(prefix + s.charAt(i), s.substring(i + 1));
    }
}  


// read in N from command line, and print all subsets among N elements
public static void main(String[] args) {
   String alphabet = "1234";
   comb2(alphabet);
   System.out.println();
}

The output generated is : 1 12 123 1234 124 13 134 14 2 23 234 24 3 34 4

Although the code is working fine. I was debugging it to understand the logic. I get how 1, 12, 123, 1234 are being generated but after that is not so clear. Can tell me whats going on here?

Answer 1

What you need to understand is how the comb2 method works. Basically, it calls itself. This is called recursion.

When you call comb2("1234"), the result is a call to comb2("","1234").

• comb2("","1234") prints "" (which has no effect), then starts a loop through the end of the string ("234"). The first thing it does in this loop is call comb2("1","234").
• comb2("1", "234") prints "1", then starts a loop through the end of the string ("234"). The first thing it does in this loop is call comb2("12","34").
• comb2("12", "34") prints "12", then starts a loop through the end of the string ("34"). The first thing it does in this loop is call comb2("123","4").
• comb2("123", "4") prints "123", then starts a loop through the end of the string ("4"). The first thing it does in this loop is call comb2("1234","").
• comb2("1234", "") prints "1234", then starts a loop through the end of the string (""). Since there is nothing to do, it returns immediately to its caller : comb2("123","4").
• comb2("123", "4") now goes to the next step in its loop. Since there is none, it returns.
• comb2("12", "34") now goes to the next step in its loop. It calls comb2("124","").
• comb2("124", "") prints "124", then starts a loop through the end of the string (""). There is nothing to do, so it returns immediately.

This is how you get from "1234" to "124". Hopefully, from there, you shoud be able to understand the whole execution.

Answer 2

The key point is comb2(prefix + s.charAt(i), s.substring(i + 1)), to understand it better please build an analogy from this statement with the cartesian product, I think this solves every thing. Indeed your'e creating all substrings starting the prefix.

Answer 3

This program should work correctly

public static void getAllSubStrings(char[] chars,int start, Set allSubStrings){
    StringBuilder sb = new StringBuilder();
    if(start==chars.length){
        return;
    }
    for(int i=start;i<chars.length;i++){
        sb.append(chars[i]);
        allSubStrings.add(sb.toString());
    }
    getAllSubStrings(chars, start+1, allSubStrings);

}
public static void main(String[] args) {
    Set s = new TreeSet();
    getAllSubStrings("12345".toCharArray(), 0, s);
    System.out.println(s);
}

Generated output is [1, 12, 123, 1234, 12345, 2, 23, 234, 2345, 3, 34, 345, 4, 45, 5]

From what I think this is still going to be O(n2) because it will run n+(n-1)+(n-2)... times which is n(n+1)/2 I don't think you can get better than that

Answer 4

Here's what a moment's noodling brought me:

import java.util.List;
import java.util.LinkedList;

public class subs {
    static List<String> allInitialSubstrings(String s) {
        List<String> r = new LinkedList<String>();
        for (int i=0; i<s.length(); i++) {
            r.add(s.substring(0, i+1));
        }
        return r;
    }

    static List<String> allSubstrings(String s) {
        List<String> r = new LinkedList<String>();
        for (int i=0; i<s.length(); i++) {
            r.addAll(allInitialSubstrings(s.substring(i)));
        }
        return r;
    }
    public static void main(String ... args) {
        System.out.println(allSubstrings(args[0]));
    }
}

~ $ javac subs.java 
~ $ java subs 12345
[1, 12, 123, 1234, 12345, 2, 23, 234, 2345, 3, 34, 345, 4, 45, 5]

If you want subsets instead of substrings, it's too much a pain in the neck for me to write it in an archaic language like Java, but here it is in the only-slightly elderly Python:

def allSubsets(s):
  if len(s):
    car = s[0]
    cdr = allSubsets(s[1:])
    return set([car + b for b in cdr]).union(cdr)
  else:
    return set([""])

allSubsets("12345")

Answer 5

Without any for loop, cleaner version with same logic would be:

public static void printSubSets(String s){
    subSetsHelper(s, "");
}

private static void subSetsHelper(String s, String acc) {
    if (s.equals("")){
        System.out.println(acc);
        return;
    }
    subSetsHelper(s.substring(1), acc + s.charAt(0)); // accumulate 1st character
    subSetsHelper(s.substring(1), acc); // do not
}

printSubSets("abc"); abc ab ac a bc b c ""