The problem
Start with a the set of positive integers 1, 2, 3, ..., N. Call that set A. Given a number 'n' satisfying 1 <= n <= N print out a set of all unique subsets of A containing n elements.
Your output should look something like this:
- N = 4 and n = 3:
- Input = Set a = [1,2,3,4], int n = 3
- Output = Set x = [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]
Breaking it down
This program was written to use Guava Set utility powerSet method which returns a set of all possible subsets of a set. For example, powerSet(ImmutableSet.of(2, 3)) returns the set {{}, {2}, {3}, {2, 3}} . To satisfy the 'n' the collection must be filtered based on the sub collection.
Create method
public static Set<Integer> generateCombinations(
Set<Integer> from,
int size) {
Set<Set<Integer>> elements = Sets.powerSet(from);
Set<Integer> possibleCombinations = elements.stream().filter(p -> p.size() == size)
.collect(Collectors.toSet());
return possibleCombinations;
}Running the program
public static void main(String[] args) {
Set<Integer> general = Sets.newHashSet(1, 2, 3, 4);
Set<Integer> combinations = generateCombinations(general, 3);
System.out.println(combinations);
}Output
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]Level Up
- Is this the most efficient way to generate combinations, if not what could be done to improve it?
- Determine other approaches could be written to solve the problem