Infinite Recursion for finding the subsets of a string?

Question

I am trying to find all the subsets of a given String. For example, the String "Rum" would have the subsets “rum”, “ru”, “rm”, “r”, “um”, “u”, “m”,and “”. Here is my code so far:

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
public class SubsetGenerator
{
    private String word;

    public SubsetGenerator(String in)
    {
        word=in;
    }
    public ArrayList<String> findSubsets()
    {
        ArrayList<String> subsets = new ArrayList<String>();
        String temp = word;
        if(temp.length()==1)
        {
            subsets.add(temp);
            return subsets;
        }
        else
        {
            String removed = temp.substring(0,1);
            temp = temp.substring(1);
            findSubsets();
            subsets.add(word);
        }
        return subsets;
    }

}

and here is the tester:

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
/**
 This program tests the subset generator.
*/
public class SubsetGeneratorTester
{
 public static void main(String[] args)
 {
 SubsetGenerator generator = new SubsetGenerator("rum");

 List<String> subsets = generator.findSubsets();
 // Sort the result for checking
 Collections.sort(subsets);
 System.out.println(subsets);
 System.out.println("Expected: [, m, r, rm, ru, rum, u, um]");
 }
}

@ifly6 an infinite recursion Exception in thread "main" java.lang.StackOverflowError at java.lang.String.substring(String.java:1969) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26) at SubsetGenerator.findSubsets(SubsetGenerator.java:26 — AnaviLucas, Feb 25 '16 at 05:30
You should look at the SO answer on [StackOverflowError](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror). — ifly6, Feb 25 '16 at 05:32
I think the main problem you're having is that you're not passing a string to evaluate into your findSubsets() method and then you're not assigning the result of findSubsets() on the recursive call. What this means, is that the program is just going to evaluate the string "rum" without ever changing the value that's evaluated by findSubsets(). Further, I don't see where you're instantiating the variable "orig" in this code--meaning it goes forever. — kondrak, Feb 25 '16 at 05:37
The value of `word` never changes, and you don't pass a parameter to your recursive method, so why would it ever stop? if the length of the parameter passed in isn't 1 to begin with, it'll just keep hitting the `else` case, doing the same thing over and over, and then calling itself again. — nbrooks, Feb 25 '16 at 05:38

Maljam · Answer 1 · 2016-02-25T05:45:18.577

0

Your method is somewhat confusing. I suggest that you use an algorithm similar to this:

public class SubsetGenerator {  
    private String word;
    private ArrayList<String> list;

    public SubsetGenerator(String word) {
        //constructor and initialize variables
    }

    void findSubsets(String str) {
         list.add(str)

         for(int i = 0 ; i < str.length() ; i++) {
             String substring = /*str with char at index i removed*/
             this.findSubsets(substring);
         }
    }
}

this should include all variants. Hope it helps.

edited Feb 25 '16 at 05:45

answered Feb 25 '16 at 05:40

Maljam

6,244
3
17
30

Removing a character from the middle of the string does not create a valid substring. – nbrooks Feb 25 '16 at 05:42
@nbrooks why not? In his question "rm" is a valid substring of "rum" – Maljam Feb 25 '16 at 05:43
You're right, I didn't realize the OP's example included that. I suppose that may be why they referred to it as a 'subset' rather than a 'substring' since, by definition, a [substring](https://en.wikipedia.org/wiki/Substring) is a string which occurs within another string. So technically what this algorithm is producing is not a substring, but a [subsequence](https://en.wikipedia.org/wiki/Subsequence). Seems to be what the OP wants though! – nbrooks Feb 25 '16 at 05:47

score 0 · Answer 2 · answered Feb 25 '16 at 09:54

I have written a recursive backtracking solution :

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
public class SubsetGenerator
{
    private String word;
    private ArrayList<String> temp;

    public SubsetGenerator(String in)
    {
        word=in;
        temp = new ArrayList<String>();
    }
    public void solve(int idx, String s){
        if(idx == word.length()){
            temp.add(s);
            return;
        }
        solve(idx+1, s + word.charAt(idx));
        solve(idx+1, s);
    }
    public ArrayList<String> findSubsets(){
        solve(0, "");
        return temp;
    }
}

Infinite Recursion for finding the subsets of a string?

2 Answers2