# How to obtain all subsequence combinations of a String (in Java, or C++ etc)

### Question

Let's say I've a string "12345" I should obtain all subsequence combinations of this string such as:

1. --> 1 2 3 4 5
2. --> 12 13 14 15 23 24 25 34 35 45
3. --> 123 124 125 234 235 345
4. --> 1234 1235 1245 1345 2345
5. --> 12345

Please note that I grouped them in different number of chars but not changed their order. I need a method/function does that.

1
19
10/26/2009 3:15:29 PM

You want a powerset. Here are all the questions on StackOverflow that mention powersets or power sets.

Here is a basic implementation in python:

``````def powerset(s):
n = len(s)
masks = [1<<j for j in xrange(n)]
for i in xrange(2**n):
yield [s[j] for j in range(n) if (masks[j] & i)]

if __name__ == '__main__':
for elem in powerset([1,2,3,4,5]):
print elem
``````

And here is its output:

``````[]


[1, 2]

[1, 3]
[2, 3]
[1, 2, 3]

[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

[1, 5]
[2, 5]
[1, 2, 5]
[3, 5]
[1, 3, 5]
[2, 3, 5]
[1, 2, 3, 5]
[4, 5]
[1, 4, 5]
[2, 4, 5]
[1, 2, 4, 5]
[3, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]
``````

Notice that its first result is the empty set. Change the iteration from this `for i in xrange(2**n):` to this `for i in xrange(1, 2**n):` if you want to skip an empty set.

Here is the code adapted to produce string output:

``````def powerset(s):
n = len(s)
masks = [1<<j for j in xrange(n)]
for i in xrange(2**n):
yield "".join([str(s[j]) for j in range(n) if (masks[j] & i)])
``````

Edit 2009-10-24

Okay, I see you are partial to an implementation in Java. I don't know Java, so I'll meet you halfway and give you code in C#:

``````    static public IEnumerable<IList<T>> powerset<T>(IList<T> s)
{
int n = s.Count;
for (int i = 0; i < n; i++)
for (int i = 0; i < (1 << n); i++)
{
List<T> newList = new List<T>(n);
for (int j = 0; j < n; j++)
if ((masks[j] & i) != 0)
yield return newList;
}
}
``````
31
5/23/2017 11:54:59 AM

way way cleaner approach can be achieved through recursion as follows.

``````Public class StrManipulation{

public static void combinations(String suffix,String prefix){
if(prefix.length()<0)return;
System.out.println(suffix);
for(int i=0;i<prefix.length();i++)
combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
}

public static void main (String args[]){
combinations("","12345");
}
}
``````