import java.util.ArrayList;

/**
     Instances of this class represent subsets of a given universal
     set of integers, and have efficient methods for stepping through 
     the subsets, returning the current subset, and finding the sum of 
     its elements.

     In fact, nowhere in the class implementation is it enforced that
     the universal set must have distinct elements, so the class 
     instances are more accurately thought of as representing bags 
     of integers.

     This class does not implement the Iterator interface, since
     the specifications for stepping through the subsets are not
     exactly the same as for an iterator.  In particular, returning
     user-friendly representations of subsets (as ArrayLists) takes
     time proportional to the size of the universal set and is
     therefore done only on demand.

     There is however a method for updating the current subset to
     the next subset in lexicographical order.  This order is 
     induced by the order of the elements in the array that the
     class constructor uses to determine the universal set, 
     together with the convention that the most rapidly changing 
     values are in the array positions with the smallest indices.
     
     Immediately after construction of an IntegerSet, the current 
     subset is empty.

     Counters are kept for the number of bits that are toggled as
     the current subset is changed (or reset), and for the number 
     of additions and subtractions performed as the current subset 
     is changed (or reset).  These are called the membership and
     addition counters in the method documentation.
     
 */


public class IntegerSet
{
	// the universal set whose subsets are to be represented
    private int[] universe;
    
    // a bit map for representing subsets of the universal set
    private boolean[] isMember;
    
    // a flag for whether the current subset is empty
    //   used so that the related query takes time O(1)
    private boolean isEmpty = true;
    
    // a counter for the number of bits (i.e., booleans)
    //   toggled in bit map manipulations
    private int membershipCounter = 0;
    
    // a counter for the number of additions and subtractions
    //   performed when finding sums of subsets
    private int additionCounter = 0;

    // the sum of the elements of the current subset    
    //   used so that the related query takes time O(1)
    private int sum = 0;
    
    
    /**
        Constructor for an IntegerSet whose underlying
          universal set is empty.  The current subset
          is initialized to the empty set.
     */
	
    public IntegerSet()                           {
      universe = new int[0];
      isMember = new boolean[0];                  }

		
    /**
       Constructor for objects of class IntegerSet.
       The current subset is initialized to the empty set.
       @param u an array representing the underlying set
     */
	
    public IntegerSet(int[] u)                           {
      universe = new int[u.length];
      isMember = new boolean[u.length];
      for (int i=0; i<u.length; i++)                  
        universe[i] = u[i];
      reset(universe);                                   } 
      
      
    /**
         Makes the empty subset the current subset.
         Updates the membership counter accordingly.
     */  
    
    private void reset(int[] u)                          {       
      sum = 0;
      isEmpty = true;
      for (int i=0; i<u.length; i++)                 {
        if (isMember[i])
          membershipCounter++;      
        isMember[i] = false;                         }   }

        
    /**
        Replaces the current subset by its lexicographical 
          successor, in amortized time O(1).  Wraps around
          so that the successor of the largest subset is
          the empty set.  Updates the membership and addition 
          counters appropriately.
     */
     // The implementation simply increments a binary integer
     //   that represents the current subset as a bit map

    public void nextSubset()                                {
      isEmpty = false;
      int i=0;
      while (isMember[i] == true && !isEmpty)         {
        isMember[i] = false;
        membershipCounter++;
        sum -= universe[i];
        additionCounter++;
        if (i==universe.length-1)                     
          isEmpty = true;  
        else
          i++;                                        }
      if (!isEmpty)                                   {
        isMember[i] = true;                            
          membershipCounter++;
        sum += universe[i]; 
          additionCounter++;                          }     }
      
      
    /**
        @return an ArrayList representation of the current subset,
          in linear time
    */

   public ArrayList<Integer> getCurrentSubset()              {
     ArrayList<Integer> result = new ArrayList<Integer>();
     for (int i=0; i<universe.length; i++)
       if (isMember[i])
         result.add(universe[i]);                         
     return result;                                          }  


   /**
        Solves the subset sum problem for the universal set
          and a given target value, in time O(2**n).  Resets the 
          current subset to the subset returned (or the empty subset
          if no subset is returned)
        @param target the target value  
        @return a subset of the universal set that sums to the
          given target if such a subset exists, or null otherwise.
    */
   
   public ArrayList<Integer> getSubsetWithSum(int target) {
     reset(universe);
     if (target == 0)
       return getCurrentSubset();
     else                                               {
       nextSubset();
       while (!isEmpty)                               {
         if (sum == target)
           return getCurrentSubset();
         else
           nextSubset();                              }
       return null;                                     } }
   
       
   /**
       @return the value of the membership counter
    */    
   
   public int getMembershipCounter()                      {
     return membershipCounter;                            }
   
     
   /**
       Optional method to reset the membership counter to 0
    */  
   
   public void resetMembershipCounter()                   {
     membershipCounter = 0;                               }
     
     
   /**
       @return the value of the addition/subtraction counter
    */    
   
   public int getAdditionCounter()                        {
     return additionCounter;                              }
     
     
   /**
       Optional method to reset the addition/subtraction
       counter to 0
    */  
   
   public void resetAdditionCounter()                     {
     additionCounter = 0;                                 }
     
     
   /**
       @return the sum of the elements of the current subset
    */  
   
   public int getCurrentSum()                             {
     return sum;                                          }
 
     
   /**
       @return <code>true</code> iff the current subset
        is the empty set
    */ 
   
   public boolean isCurrentSubsetEmpty()                  {
     return isEmpty;                                      }
         
}