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

Assumptions

• There could be duplicate characters in the original set.

​Examples

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

Solution 1: 先把input sort，在每层recursion，从index iterate到尾，input[i] == input[i - 1]时跳过，只选第一个duplicate

  public List<String> subSets(String set) {
    if (set == null) {
      return new ArrayList<String>();
    }
    List<String> ans = new ArrayList<>();
    char[] chars = set.toCharArray();
    Arrays.sort(chars);
    helper(0, new StringBuilder(), ans, chars);
    return ans;
  }
  private void helper(int index, StringBuilder path, List<String> ans, char[] set) {
    //注意在开头就加入ans，比如空subset
    ans.add(path.toString());
    for (int i = index; i < set.length; i++) {
      if (i > index && set[i] == set[i - 1]) {
        continue;
      }
      path.append(set[i]);
      helper(i + 1, path, ans, set);
      path.deleteCharAt(path.length() - 1);
    }
  }

Solution 2: 每个字符有加或不加两种情况，若选择不加，则把所有的duplicates跳过