/*
* 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
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);
}
}