Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There are no duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]
• Set = "", all the subsets are [""]
• Set = null, all the subsets are []

 

time: O(2 ^ n), space: O(2 ^ n)

public class Solution {  public List
     
       subSets(String set) {    // Write your solution here.    List
      
        res = new ArrayList<>();    if(set == null) {      return res;    }    dfs(set, 0, new StringBuilder(), res);    return res;  }    private void dfs(String set, int idx, StringBuilder sb, List
       
         res) {    if(idx == set.length()) {      res.add(sb.toString());      return;    }        sb.append(set.charAt(idx));    dfs(set, idx + 1, sb, res);    sb.deleteCharAt(sb.length() - 1);        dfs(set, idx + 1, sb, res);  }}