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:
if index == set.length() base case is not addressed, stackoverflow or indexoutofbounds error will occur
DONT INCREMENT K. NO TOUCHE
Remember to clarify edge cases
Last updated
Was this helpful?