// Here are the solutions to the warmup problems given in Assignment 3. /* * Function: PrintInBinary * ----------------------- * Uses recursion to print the binary representation (base-two) of * a given number. The parameter is expected to be non-negative. */ void PrintInBinary(int number) { if (number > 1) PrintInBinary(number/2); // recursively print rest of binary digits cout << (number % 2); // now print least signficant binary digit } /* * Function: RecSum * ---------------- * Recursive function to explore all possible subsets in attempt to * find one that sums to target value. The parameters are the vector * of numbers, the index of the next element to consider, the sum so far, * and the target value. If the sum so far is equal to the target, we * have found the desired subset and can immediately return true. * If we have run out of elements to try, we return false. Otherwise, * take the next vector element and try it both in and out, stopping as soon * as we find a successful subset. This in-out pattern is commonly * used for any sort of subset/power-set exploration. */ bool RecSum(Vector & nums, int index, int sumSoFar, int target) { if (sumSoFar == target) return true; // success base case if (index == nums.size()) return false; // failure base case // recursive case, try next element both in and out of the sum return RecSum(nums, index+1, sumSoFar, target) || RecSum(nums, index+1, sumSoFar+nums[index], target); } /* * Function: AltRecSum * ------------------- * Same goal as function RecSum described above, but uses a different * recursive pattern to compute result. Instead of considering one * element at each call and trying it both in/out, this version * chooses an element to add on each call by picking one of the * remaining elements and discarding any elements in between. * This is the choose-one-of-remaining pattern, such as used * for generating permutations. */ bool AltRecSum(Vector & nums, int index, int sumSoFar, int target) { if (sumSoFar == target) return true; // success base case // can include same explicit failure case as above, or let fall // through (loop will not execute) for (int i = index; i < nums.size(); i++) { if (RecSum(nums, i+1, sumSoFar+nums[i], target)) return true; } return false; } /* * Function: CanMakeSum * -------------------- * Given an vector of numbers and a target sum, reports whether any * subset of the numbers in the array sum to that target. This is * just a wrapper for the recursive function RecSum (or could call * AltRecSum for same result). */ bool CanMakeSum(Vector & nums, int targetSum) { return RecSum(nums, 0, 0, targetSum); }