cannot have overlapping triominoes or triominoes which extend out of the mboard (aan mboard (bfour mboards figure mutilated chessboards divide-and-conquer is good strategy for this problem instead of the mboardlet' consider an mboard mboard can be covered with one triomino since it is of the same exact shape you may hypothesize that triomino placement for an mboard with the top-left square missing can be used to compute placement for an ( ( mboard howeveryou will quickly see that this line of reasoning does not lead you anywhere another hypothesis is that if placement exists for an mboardthen one also exists for mboard now we can apply divide-and-conquer take four mboards and arrange them to form square in such way that three of the mboards have their missing square set towards the center and one mboard has its missing square outward to coincide with the missing corner of mboardas shown in figure (bthe gap in the center can be covered with triomino andby hypothesiswe can cover the four mboards with triominoes as well hencea placement exists for any that is power of in particulara placement exists for the mboardthe recursion used in the proof directly yields the placement generate the power set the power set of set is the set of all subsets of sincluding both the empty set and itself the power set of { is graphically illustrated in figure on the next page write function that takes as input set and returns its power set hintthere are subsets for given set of size there are -bit words solutiona brute-force way is to compute all subsets that do not include particular element (which could be any single elementthen we compute all subsets which do include that element each subset set must appear in or in vso the final result is just uv the construction is recursiveand the base case is when the input set is emptyin which case we return {{}