CodeStepByStep

Write a recursive function named canPack that accepts information about a collection of bags of given sizes, and a collection of items of various sizes, and returns true if the given bags can hold all of the given items successfully. Use backtracking to try combinations of packing items into different bags, looking for a successful arrangement.

In this problem, a bag is a container (such as a backpack) that can store items inside of it. Bags and items are represented as integers: An integer for an item represents its size, and an integer for a bag represents the total size of items that can be stored inside it. For example, a bag of size 7 could store an item of size 7; or an item of size 5 and an item of size 2; or seven items of size 1; or any other combination up to a total size of 7 for the combined items inside it. A bag can be partially filled if necessary; a bag of size 7 could store items whose total weight is any number up to 7 inclusive.

Your function will accept two parameters. The first is a reference to a vector of integers representing the sizes of the available bags. For example, the vector {4, 8, 3, 3} means that you have four bags available with sizes of 4, 8, 3, and 3 respectively. The second parameter to your function is a reference to a vector of integers representing the available items. For example, the vector {2, 3, 2, 5, 4, 1} means that you have six items of sizes 2, 3, 2, 5, 4, and 1 respectively. Your function's task is to see if the given items can fit into the given bags in some combination. With this example vector of bags and of items, the function would return true because the items can be fit into the bags successfully. One successful arrangement is that the first bag of size 4 holds the size-4 item; the second bag of size 8 holds the size-3 and size-5 items; the third bag of size 3 holds a size-2 item, and the fourth bag of size 3 holds the other size-2 item and the size-1 item. The diagram below attempts to show this arrangement:

                                    [2,2]   [3,5]   [2]  [2,1]
bags:  {4, 8, 3, 3}           -->    {4,      8,     3,    3}   items in bags
items: {2, 3, 2, 5, 4, 1}

Below are several examples of combinations of bags and items where your function should return false, because there exists no combination where the items can be packed into the bags without overflowing.

bags:  {12, 10}
items: {8, 6, 7}

{5, 5, 5}
{3, 3, 3, 3}

{1, 1, 5, 7, 9}
{2, 4, 6, 8}

{}
{1}

If no items are passed (that is, if the collection of items passed is empty), your function should return true.

The collections passed to your function must be back to their original state at the end of the call. Either do not modify them, or if you modify them, fully undo your modifications before the function returns.

Hint: The point is not to devise a clever pattern or algorithms for finding the best packing strategy. The idea is to just try all possible choices of items in various bags until you find an arrangement that works.

For the most part you do not need to worry about efficiency, but your code should not perform exactly the same unnecessary deep exploration multiple times. You should also avoid making copies of data structures extremely high numbers of times by always passing them by reference.

Constraints: Do not declare any global variables. You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking. You are allowed to define other "helper" functions if you like; they are subject to these same constraints.