//ShoppingSpreeCombinations.java

import java.util.ArrayList;

public class ShoppingSpreeCombinations
{
    // Max number of items in shopping bag
    public static final int MAX_SHOPPING_BAG_SIZE = 3;

    /* Output every combination of items that fit
       in a shopping bag. Each recursive call moves
       one item into the shopping bag.
    */
    public static void shoppingBagCombinations
    (
        ArrayList<GroceryItem> currBag, // Bag contents
        ArrayList<GroceryItem> remainingItems // Available items
    )
    {
        int bagValue;               // Cost of items in shopping bag
        GroceryItem tmpGroceryItem; // Grocery item to add to bag
        int i;                      // Loop index

        // Base case: Shopping bag full
        if (currBag.size() == MAX_SHOPPING_BAG_SIZE)
        {
            bagValue = 0;
            for (i = 0; i < currBag.size(); ++i)
            {
                bagValue += currBag.get(i).priceDollars;
                System.out.print(currBag.get(i).itemName + "  ");
            }
            System.out.println("= $" + bagValue);
        }
        else // Recursive case: move one
        {
            for (i = 0; i < remainingItems.size(); ++i) // item to bag
            {
                // Move item into bag
                tmpGroceryItem = remainingItems.get(i);
                remainingItems.remove(i);
                currBag.add(tmpGroceryItem);

                shoppingBagCombinations(currBag, remainingItems);

                // Take item out of bag
                remainingItems.add(i, tmpGroceryItem);
                currBag.remove(currBag.size() - 1);
            }
        }
    }

    public static void main(String[] args)
    {
        ArrayList<GroceryItem> possibleItems = new
        ArrayList<GroceryItem>(); // Possible shopping items
        ArrayList<GroceryItem> shoppingBag = new
        ArrayList<GroceryItem>(); // Current shopping bag
        GroceryItem
        tmpGroceryItem; // Temp item

        // Populate grocery with different items
        tmpGroceryItem = new GroceryItem();
        tmpGroceryItem.itemName = "Milk";
        tmpGroceryItem.priceDollars = 2;
        possibleItems.add(tmpGroceryItem);

        tmpGroceryItem = new GroceryItem();
        tmpGroceryItem.itemName = "Belt";
        tmpGroceryItem.priceDollars = 24;
        possibleItems.add(tmpGroceryItem);

        tmpGroceryItem = new GroceryItem();
        tmpGroceryItem.itemName = "Toys";
        tmpGroceryItem.priceDollars = 19;
        possibleItems.add(tmpGroceryItem);

        tmpGroceryItem = new GroceryItem();
        tmpGroceryItem.itemName = "Cups";
        tmpGroceryItem.priceDollars = 12;
        possibleItems.add(tmpGroceryItem);

        // Try different combinations of three items
        shoppingBagCombinations(shoppingBag, possibleItems);
    }
}