Generating power set recursively without any loops

Question

How do you write a recursive method PowerSet(String input) that prints out all possible combinations of a string that is passed to it? For example: PowerSet("abc") will print out abc, ab, ac, bc, a, b, c I have seen some recursive solutions with loops, but in this case no loops are allowed. Any ideas? Edit: The required method has only one parameter, i.e. String input.

Accepted Answer

The powerset of `abcd` is the union of the power-sets of `abc`, `abd`, `acd` (plus the set `abcd` itself*).

```
 P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)
```

* Note that the empty set, which is a member of P(abcd) is also a member of P(abc), P(abd), ... so the equivalence stated above holds.

Recursively, P(`abc`) = {`abc`} + P(`ab`) + P(`ac`), and so on

A first approach, in pseudocode, could be:

```
powerset(string) {
  add string to set;
  for each char in string {
   let substring = string excluding char,
   add powerset(substring) to set
  }
  return set;      
}
```

The recursion ends when the string is empty (because it never enters the loop).

If your really want no loops, you will have to convert that loop to another recursion. Now we want to generate `ab`, `ac` and `cb` from `abc`

```
powerset(string) {
  add string to set;
  add powerset2(string,0) to set;
  return set
}

powerset2(string,pos) {
  if pos<length(string) then
    let substring = (string excluding the char at pos)
    add powerset(substring) to set
    add powerset2(string,pos+1) to set
  else 
    add "" to set
  endif
  return set
}
```

Another approach implement a recursive function `P` that either removes the first character from its argument, or does not. (Here `+` means set union, `.` means concatenation and `λ` is the empty string)

```
P(abcd) = P(bcd) + a.P(bcd)
P(bcd)  = P(cd)  + b.P(cd)
P(cd)   = P(d)   + c.P(d)
P(d)    = λ+d //particular case
```

Then

```
P(d)    = λ+d
R(cd)   = P(d)  + c.P(d)  = λ + d + c.(λ+d) = λ + d + c + cd
R(bcd)  = P(cd) + b.P(cd) = λ + d + c + cd + b.(λ + d + c + cd)
                          = λ + d + c + cd + b + bd + bc + bcd
P(abcd) =  λ +  d +  c +  cd +  b +  bd +  bc +  bcd 
        + aλ + ad + ac + acd + ab + abd + abc + abcd 
```

If loops were allowed, then `P` is out power-set function. Otherwise, we would need a one-parameter loopless function for concatenating a given character to a given set of strings (which obviously are two things).

Some tweak could be possible by playing with `String.replace` (if a `String` result is desired, or by replacing `Set` with `List` (so that the "additional" parameter is actually the first element in the list).

Generating power set recursively without any loops

Solution

Problem

Related problems