All subsets size k

Medium

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

Assumptions

There are no duplicate characters in the original set.

​Examples

Set = "abc", K = 2, all the subsets are [“ab”, “ac”, “bc”].

Set = "", K = 0, all the subsets are [""].

Set = "", K = 1, all the subsets are [].

public class Solution {
  public List<String> subSetsOfSizeK(String set, int k) {
    List<String> result = new ArrayList<>();
    if (k == 0) {
      result.add("");
      return result;
    }

    if (set == null || set.length() == 0 || k > set.length()) {
      return result;
    }

    helper(set, k, new StringBuilder(), 0, result);
    return result;
  }

  public void helper(String set, int k, StringBuilder sb, int index, List<String> results) {
    if (sb.length() == k) {
      results.add(sb.toString());
      return;
    }

    if (index == set.length()) {
      return;
    }

    // case 1: do not use char at index
    helper(set, k, sb, index + 1, results);

    // case 2: use char at index
    sb.append(set.charAt(index));
    helper(set, k, sb, index + 1, results);
    
    sb.deleteCharAt(sb.length() - 1);  
  }
}

Mistakes Made:

  1. if index == set.length() base case is not addressed, stackoverflow or indexoutofbounds error will occur

  2. DONT INCREMENT K. NO TOUCHE

  3. Remember to clarify edge cases

Last updated

Was this helpful?