Subsets

• What is a subset ?
• Build up intuition.
• Print lexicographically.
• Handling duplicates.

What is a subset?

A set X can be called a subset of Y if all elements of X are present in Y.

    How to generate all subsets ?
    0 length subsets - {}
    1 length subsets - {1}, {2}, {3}, ... {n}
    2 length subsets - {1,2}, {1,n}, {2,3}.. , {2,n}.. {n-1,n}
    n length subsets - {1,n}
    Total subsets = nc0 + nc1 + ...  + ncn = 2^n

		

Build up intuition.

Here the inseresting thing to note in a subset X is that any element from Y can be present or absent, so, basically we have 2 choices at a given point to either include the element or exclude the element. At every step we either include the element or exclude it.

ip 123 op =””
we are at 1, we can either select or reject it.
1 {}
same here select 2 or reject it
12 1 2 {}
same 3 can be selected or rejected.

123 12 13 1 23 2 3 {} -> last level.

void subsets(string & input, string output, int index) {
    if(input.size() == index) {
        cout << output <<endl;
        return;
    }
    char temp = input[index];

    // Include the character from index.
    subsets(input, output +  temp, index+1);
   // Exclude the character from index.
    subsets(input, output, index+1);
}

Print lexicographically.

Now, let’s try to generate subsets in sorted order, simplest way is to add to sort the output and print.

	void subsets_sorted(string & input, string output, int index, vector<string> & result) {
		if(input.size() == index) {
			result.push_back(output);
			return;
		}
		char temp = input[index];
	
		subsets_sorted(input, output +  temp, index+1, result);
		subsets_sorted(input, output, index+1, result);
	}

// sort the vector.
sort(result.begin(), result.end());

The disadvantage is to sort the vector, which itself takes nlogn time. Is there a way we can do without sorting explictly?

Let’s analyze the output in sorted order for set {1,2,3}

{}, 1, 12, 123, 13, 2, 23, 3

This can be achieved with 3 for loops,

	for (int i = 1; i <= 3; i++) {
		cout << i <<endl;
		for (int j = i+1; j <= 3; j++) {
			cout << i << j <<endl;
			for (int k = j+1; k<= 3; k++) {
			cout << i << j << k << endl;
			}
		}
	
	}

looks easy, but for some “n”, we can’t increase for loops in this manner, so we need something which can configure dynamically based on n?

How about a recursive method inside a for loop:
-> For first level for recursion it can go from 0 -> size
-> for next level it can go from 1-> size
-> for 2->size
and at every level we get 1 subset, the outermost loop which is running will first create subset of element 1 , then element 2 , so on.

	void subsetsLoop(string & input, string output, int index) {
		cout << output <<endl;
		for(int i = index ; i < input.size(); i++) {
			subsetsLoop(input, output +  input[i], i+1, count);
		}
	}

Handling duplicates

If the given input is 112 -> {} , {1}, {1}, {2}, {1,1} {1,2}, {1,2} , {1,2,3}

Out of these {1}, {1,2} are repeated. The above code can’t handle these. we know that because of recursion there are some paths which will be repeated.
For example 1,1,2, -> 12 can be by selecting first 1 and 2 as well as by selecting second 1 and 2.
so when you are on de-selection path (1,1,2 ) -> { 1st 1 not selected, then you should not start choices from the next one, as it will repeat the same choice done by 1st one, so until we find the same, we increase the index }

/ **  
*  For looping skip the element during loop
*  if previous element is same as current,
*  so no need to have its combinations.
*/
    void subsetsLoop(string & input, string output, int index) {
        cout << output <<endl;
        for(int i = index ; i < input.size(); i++) {
/ **
* you are in a loop to select an element
*  which is similiar to previous, skip that.
*/
            if(i > index && input[i] == input[i-1]) continue;  
            subsetsLoop(input, output +  input[i], i+1);
        }
    }

    void subsets(string & input, string output, int index) {
        if(input.size() == index) {
            cout << output <<endl;
            return;
        }
        char temp = input[index];
    
        subsets(input, output +  temp, index+1);
/ **
* When you are deselecting a element,
* make sure next is not same, skip to distinct.
*/
        while(index != input.size() && input[index] == input[index+1]) 
            index++;
        subsets(input, output, index+1);
    }