Subset Problems

In this post, I would discuss some basic programming problems on sets.

Problem Statement:

Given a list of numbers, find all the possible subsets of the list of numbers. For example, if the set of numbers given is {1,2,3}, the output should be {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}.

Solution:

The first solution is recursive is pretty straight forward. Please follow the Java code given below.

The second solution is iterative and is more efficient than the first solution. This solution works based on the principle that for a set of n elements, there would 2^n subsets. The binary representation of an integer i in the range 0 to (2^n - 1) is used to find the corresponding ith subset. For example, if there are 3 elements in the set, we enumerate the binary representation of all the numbers from 0 to 7. Each binary representation represents a subset. The set bit at ith index represents that take ith element from the set. Here are those :
000 -> Empty set
001 -> Only take 1st element
010 -> Only take 2nd element
011 -> Take 1st and 2nd element
100 -> Only take 3rd element
101 -> Take 1st and 3rd element
110 -> Take 2nd and 3rd element
111 -> Take all elements

If we tweek the above problem statement a little. Here is the new problem statement:

Problem Statement:

Given a list of numbers from 0-9, find the greatest number that can be formed from these numbers such that the number is divisible by three

Solution:

We can use the recursive approach above. One more property is needed : If a number is divisible by 3, then the sum of its digits is also divisible by three. Since we have to find the greatest number, we can start with the greatest number in the recursive solution above. Also the list need to be reverse  sorted so that the smallest number is removed first. Here is the code segment :