Write a recursive c++ program that will output all the subsets of a set of n ele

Question

Write a recursive c++ program that will output all the subsets of a set of n elements without repeating any subsets.

Explanation / Answer

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}. If S has n elements in it then P(s) will have 2^n elements 1st using Recursion public class PowerSet { private void printPowerSet(String inputString, String prefixString, int startIndex){ if(inputString == null){ return; } for(int i=startIndex;iString str = ""; str = prefixString + inputString.charAt(i); System.out.println("{" + str + "} "); printPowerSet(inputString, str, i+1); } } public static void main(String args[]){ String inputStr ="123"; System.out.println("{ } "); for(int i=0; iPowerSet powerSet = new PowerSet(); System.out.println("{" + inputStr.charAt(i) + "} "); powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1); } } } TC O(n^2) Sc O(n) Run here https://ideone.com/8RuF1 2nd Iterative Method Algorithm: Input: Set[], set_size 1. Get the size of power set powet_set_size = pow(2, set_size) 2 Loop for counter from 0 to pow_set_size (a) Loop for i = 0 to set_size (i) If ith bit in counter is set Print ith element from set for this subset (b) Print seperator for subsets i.e., newline Example: Set = [a,b,c] power_set_size = pow(2, 3) = 8 Run for binary counter = 000 to 111 Value of Counter Subset 000 -> Empty set 001 -> a 011 -> ab 100 -> c 101 -> ac 110 -> bc 111 -> abc #include #include void printPowerSet(char *set, int set_size) { /*set_size of power set of a set with set_size n is (2**n -1)*/ unsigned int pow_set_size = pow(2, set_size); int counter, j; /*Run from counter 000..0 to 111..1*/ for(counter = 0; counter 1; } System.out.println(); number++; } } public static void main(String[] args) { PowerSet p=new PowerSet(); p.powerSet(); System.out.println("Total number of subsets are"+p.number); } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.