To generate all the k-element subsets from a n-element set (n>k), there is a recursive solution - add a particular element to all the (k-1) element subsets.Follow the same step to get all (k-1) element subsets.
I have been unable to put the above idea to code.Could someone help?
2 Likes
Are you familiar with the standard algorithm for generating all possible subsets of a particular set? It is simply based on inclusion and exclusion of a particular element and you keep recursing on the remaining part of the set.
For this question you can pass another argument CountOfElements to the function which keep track of the number of elements currently chosen by the function. every time you select an element increase this count by 1 and pass to the function. If you exclude the element pass the previous count.
Once this count reaches k elements, you print/select this set and return.The normal subset algorithm has a complexity of O(2^N) and this algorithm will also be exponential.
There are better algorithms which use bit manipulation .Brief explanation : Take a string or array of length n with exactly k 1’s in it and generate all permutations of this string. In each permutation ,wherever you get 1 choose that element else exclude it.this algorithm will also give you all k element subsets.
3 Likes
can u provide me link for inclusion and exclusion principle??