Question

/*
 *  Target Practice 01 - Recursion
 *
 *  Problem 1:  Powerset - Helper Method Recursion
 *
 *  Prompt:   Given a set S, return the powerset P(S), which is
 *            a set of all subsets of S.
 *
 *  Input:    {String}
 *  Output:   {Array}
 *
 *  Example:  S = "abc", P(S) = ['', 'a', 'b','c','ab','ac','bc','abc']
 *
 *  Notes:     The input string will not contain duplicate characters
 *            The letters in the subset string must be in the same order
 *            as the original input.
 */

Diagramming

Powerset

Solution

class Powerset {

	public static List<String> result;
  public static List<String> compute(String str) {
    // YOUR WORK HERE
	  result = new ArrayList<String>();
	  createPowerSet(str, "", 0);
    return result;
  }

  private static void createPowerSet(String str, String curr, int index) {
	  
	  //base case
	  if(index == str.length()) {
		  result.add(curr);
		  return;
	  }
	  
	  //call method with current string and index+1
	  createPowerSet(str, curr, index+1);
	  
	  //call method with current string + character at index and index+1
	  createPowerSet(str, curr + str.charAt(index), index+1);
  }
}