Popular Posts

  • Robot in an NXN grid
    Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ...
  • CLRS Exercises 2.3-4 Recursive insertion sort
    Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
  • Kth Largest from an infinite stream
    Problem:   Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
  • Print BST keys in the given range
    Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i....
  • Simultaneous minimum and maximum
    How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
  • CLRS Exercises 2.3-7
    Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
  • Delete alternate nodes of a Linked List
    Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
  • Print Ancestors of a given node in Binary Tree
    Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
  • CLRS - Problem 2.1
    Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
  • CLRS Exercises 5.1-2
    Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...

Monday, July 18, 2011

PowerSet

Problem:
Write a method that returns all subsets of a set.
Solution:
Recursive approach:

  • The set of subsets of {1} is {{}, {1}}
  • For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
  • Repeat till you reach n

Complexity: O(2^n)
Code:

Iterative Approach:
Posted by anantha at 7/18/2011 04:27:00 PM
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)