cpp-codingbat-13-Recursion-2.ipynb


{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
	"#include <iostream>\n",
	"#include <iomanip>\n",
	"#include <vector>\n",
	"\n",
	"using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
	"namespace testns { template<class A> void printTest( string str, A run, A expected )\n",
	"{\n",
	"    if( run == expected )\n",
	"        cout << boolalpha << \"\\033[1;32m\"\n",
	"            << \"Expected: \" << setw(60) << left << str << \" Run: \" << setw(20) << left << run << \"\\t\\tOK\"\n",
	"            << \"\\033[0m\" << endl;\n",
	"    else\n",
	"        cerr << boolalpha << \"\\033[1;31m\"\n",
	"            << \"Expected: \" << setw(60) << left << str << \" Run: \" << setw(20) << left << run << \"\\t\\tX\"\n",
	"            << \"\\033[0m\" << endl;\n",
	"} } using namespace testns;\n",
	"void printTest( string str, string run, const char* expected ){ printTest( str, \"\\\"\"+run+\"\\\"\", \"\\\"\"+string( expected )+\"\\\"\" ); }\n",
	"template<class A> void printTest( string str, vector<A> run, vector<A> expected )\n",
	"{\n",
	"    string runStr = \"[\"; for( A a : run ) runStr += to_string( a ) + \", \";\n",
	"    if( runStr.length() > 1 ) runStr = runStr.substr(0, runStr.length()-2); runStr += \"]\";\n",
	"    string expStr = \"[\"; for( A a : expected ) expStr += to_string( a ) + \", \";\n",
	"    if( expStr.length() > 1 ) expStr = expStr.substr(0, expStr.length()-2); expStr += \"]\";\n",
	"    printTest( str, runStr, expStr );\n",
	"}"
   ]
  },
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > groupSum"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to choose a group of some of the ints,\n", "such that the group sums to the given target? This is a classic backtracking\n", "recursion problem. Once you understand the recursive backtracking strategy in\n", "this problem, you can use the same pattern for many problems to search a space\n", "of choices. Rather than looking at the whole array, our convention is to\n", "consider the part of the array starting at index start and continuing to the end\n", "of the array. The caller can specify the whole array simply by passing start as\n", "0. No loops are needed -- the recursive calls progress down the array.\n", "\n", "groupSum(0, [2, 4, 8], 10) \u2192 true\n", "groupSum(0, [2, 4, 8], 14) \u2192 true\n", "groupSum(0, [2, 4, 8], 9) \u2192 false\n", "*/\n", "\n", "bool groupSum(int start, vector<int> nums, int target) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"groupSum(0, [2, 4, 8], 10) \u2192 true\", groupSum(0, {2, 4, 8}, 10), true );\n", "printTest( \"groupSum(0, [2, 4, 8], 14) \u2192 true\", groupSum(0, {2, 4, 8}, 14), true );\n", "printTest( \"groupSum(0, [2, 4, 8], 9) \u2192 false\", groupSum(0, {2, 4, 8}, 9), false );\n", "printTest( \"groupSum(0, [2, 4, 8], 8) \u2192 true\", groupSum(0, {2, 4, 8}, 8), true );\n", "printTest( \"groupSum(1, [2, 4, 8], 8) \u2192 true\", groupSum(1, {2, 4, 8}, 8), true );\n", "printTest( \"groupSum(1, [2, 4, 8], 2) \u2192 false\", groupSum(1, {2, 4, 8}, 2), false );\n", "printTest( \"groupSum(0, [1], 1) \u2192 true\", groupSum(0, {1}, 1), true );\n", "printTest( \"groupSum(0, [9], 1) \u2192 false\", groupSum(0, {9}, 1), false );\n", "printTest( \"groupSum(1, [9], 0) \u2192 true\", groupSum(1, {9}, 0), true );\n", "printTest( \"groupSum(0, [], 0) \u2192 true\", groupSum(0, {}, 0), true );\n", "printTest( \"groupSum(0, [10, 2, 2, 5], 17) \u2192 true\", groupSum(0, {10, 2, 2, 5}, 17), true );\n", "printTest( \"groupSum(0, [10, 2, 2, 5], 15) \u2192 true\", groupSum(0, {10, 2, 2, 5}, 15), true );\n", "printTest( \"groupSum(0, [10, 2, 2, 5], 9) \u2192 true\", groupSum(0, {10, 2, 2, 5}, 9), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > groupSum6"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to choose a group of some of the ints,\n", "beginning at the start index, such that the group sums to the given target?\n", "However, with the additional constraint that all 6\u02bcs must be chosen. (No loops\n", "needed.)\n", "\n", "groupSum6(0, [5, 6, 2], 8) \u2192 true\n", "groupSum6(0, [5, 6, 2], 9) \u2192 false\n", "groupSum6(0, [5, 6, 2], 7) \u2192 false\n", "*/\n", "\n", "bool groupSum6(int start, vector<int> nums, int target) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"groupSum6(0, [5, 6, 2], 8) \u2192 true\", groupSum6(0, {5, 6, 2}, 8), true );\n", "printTest( \"groupSum6(0, [5, 6, 2], 9) \u2192 false\", groupSum6(0, {5, 6, 2}, 9), false );\n", "printTest( \"groupSum6(0, [5, 6, 2], 7) \u2192 false\", groupSum6(0, {5, 6, 2}, 7), false );\n", "printTest( \"groupSum6(0, [1], 1) \u2192 true\", groupSum6(0, {1}, 1), true );\n", "printTest( \"groupSum6(0, [9], 1) \u2192 false\", groupSum6(0, {9}, 1), false );\n", "printTest( \"groupSum6(0, [], 0) \u2192 true\", groupSum6(0, {}, 0), true );\n", "printTest( \"groupSum6(0, [3, 2, 4, 6], 8) \u2192 true\", groupSum6(0, {3, 2, 4, 6}, 8), true );\n", "printTest( \"groupSum6(0, [6, 2, 4, 3], 8) \u2192 true\", groupSum6(0, {6, 2, 4, 3}, 8), true );\n", "printTest( \"groupSum6(0, [5, 2, 4, 6], 9) \u2192 false\", groupSum6(0, {5, 2, 4, 6}, 9), false );\n", "printTest( \"groupSum6(0, [6, 2, 4, 5], 9) \u2192 false\", groupSum6(0, {6, 2, 4, 5}, 9), false );\n", "printTest( \"groupSum6(0, [3, 2, 4, 6], 3) \u2192 false\", groupSum6(0, {3, 2, 4, 6}, 3), false );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 4], 12) \u2192 true\", groupSum6(0, {1, 6, 2, 6, 4}, 12), true );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 4], 13) \u2192 true\", groupSum6(0, {1, 6, 2, 6, 4}, 13), true );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 4], 4) \u2192 false\", groupSum6(0, {1, 6, 2, 6, 4}, 4), false );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 4], 9) \u2192 false\", groupSum6(0, {1, 6, 2, 6, 4}, 9), false );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 5], 14) \u2192 true\", groupSum6(0, {1, 6, 2, 6, 5}, 14), true );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 5], 15) \u2192 true\", groupSum6(0, {1, 6, 2, 6, 5}, 15), true );\n", "printTest( \"groupSum6(0, [1, 6, 2, 6, 5], 16) \u2192 false\", groupSum6(0, {1, 6, 2, 6, 5}, 16), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > groupNoAdj"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to choose a group of some of the ints,\n", "such that the group sums to the given target with this additional constraint: If\n", "a value in the array is chosen to be in the group, the value immediately\n", "following it in the array must not be chosen. (No loops needed.)\n", "\n", "groupNoAdj(0, [2, 5, 10, 4], 12) \u2192 true\n", "groupNoAdj(0, [2, 5, 10, 4], 14) \u2192 false\n", "groupNoAdj(0, [2, 5, 10, 4], 7) \u2192 false\n", "*/\n", "\n", "bool groupNoAdj(int start, vector<int> nums, int target) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"groupNoAdj(0, [2, 5, 10, 4], 12) \u2192 true\", groupNoAdj(0, {2, 5, 10, 4}, 12), true );\n", "printTest( \"groupNoAdj(0, [2, 5, 10, 4], 14) \u2192 false\", groupNoAdj(0, {2, 5, 10, 4}, 14), false );\n", "printTest( \"groupNoAdj(0, [2, 5, 10, 4], 7) \u2192 false\", groupNoAdj(0, {2, 5, 10, 4}, 7), false );\n", "printTest( \"groupNoAdj(0, [2, 5, 10, 4, 2], 7) \u2192 true\", groupNoAdj(0, {2, 5, 10, 4, 2}, 7), true );\n", "printTest( \"groupNoAdj(0, [2, 5, 10, 4], 9) \u2192 true\", groupNoAdj(0, {2, 5, 10, 4}, 9), true );\n", "printTest( \"groupNoAdj(0, [10, 2, 2, 3, 3], 15) \u2192 true\", groupNoAdj(0, {10, 2, 2, 3, 3}, 15), true );\n", "printTest( \"groupNoAdj(0, [10, 2, 2, 3, 3], 7) \u2192 false\", groupNoAdj(0, {10, 2, 2, 3, 3}, 7), false );\n", "printTest( \"groupNoAdj(0, [], 0) \u2192 true\", groupNoAdj(0, {}, 0), true );\n", "printTest( \"groupNoAdj(0, [1], 1) \u2192 true\", groupNoAdj(0, {1}, 1), true );\n", "printTest( \"groupNoAdj(0, [9], 1) \u2192 false\", groupNoAdj(0, {9}, 1), false );\n", "printTest( \"groupNoAdj(0, [9], 0) \u2192 true\", groupNoAdj(0, {9}, 0), true );\n", "printTest( \"groupNoAdj(0, [5, 10, 4, 1], 11) \u2192 true\", groupNoAdj(0, {5, 10, 4, 1}, 11), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > groupSum5"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to choose a group of some of the ints,\n", "such that the group sums to the given target with these additional constraints:\n", "all multiples of 5 in the array must be included in the group. If the value\n", "immediately following a multiple of 5 is 1, it must not be chosen. (No loops\n", "needed.)\n", "\n", "groupSum5(0, [2, 5, 10, 4], 19) \u2192 true\n", "groupSum5(0, [2, 5, 10, 4], 17) \u2192 true\n", "groupSum5(0, [2, 5, 10, 4], 12) \u2192 false\n", "*/\n", "\n", "bool groupSum5(int start, vector<int> nums, int target) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 19) \u2192 true\", groupSum5(0, {2, 5, 10, 4}, 19), true );\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 17) \u2192 true\", groupSum5(0, {2, 5, 10, 4}, 17), true );\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 12) \u2192 false\", groupSum5(0, {2, 5, 10, 4}, 12), false );\n", "printTest( \"groupSum5(0, [2, 5, 4, 10], 12) \u2192 false\", groupSum5(0, {2, 5, 4, 10}, 12), false );\n", "printTest( \"groupSum5(0, [3, 5, 1], 4) \u2192 false\", groupSum5(0, {3, 5, 1}, 4), false );\n", "printTest( \"groupSum5(0, [3, 5, 1], 5) \u2192 true\", groupSum5(0, {3, 5, 1}, 5), true );\n", "printTest( \"groupSum5(0, [1, 3, 5], 5) \u2192 true\", groupSum5(0, {1, 3, 5}, 5), true );\n", "printTest( \"groupSum5(0, [3, 5, 1], 9) \u2192 false\", groupSum5(0, {3, 5, 1}, 9), false );\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 7) \u2192 false\", groupSum5(0, {2, 5, 10, 4}, 7), false );\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 15) \u2192 true\", groupSum5(0, {2, 5, 10, 4}, 15), true );\n", "printTest( \"groupSum5(0, [2, 5, 10, 4], 11) \u2192 false\", groupSum5(0, {2, 5, 10, 4}, 11), false );\n", "printTest( \"groupSum5(0, [1], 1) \u2192 true\", groupSum5(0, {1}, 1), true );\n", "printTest( \"groupSum5(0, [9], 1) \u2192 false\", groupSum5(0, {9}, 1), false );\n", "printTest( \"groupSum5(0, [9], 0) \u2192 true\", groupSum5(0, {9}, 0), true );\n", "printTest( \"groupSum5(0, [], 0) \u2192 true\", groupSum5(0, {}, 0), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > groupSumClump"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to choose a group of some of the ints,\n", "such that the group sums to the given target, with this additional constraint:\n", "if there are numbers in the array that are adjacent and the identical value,\n", "they must either all be chosen, or none of them chosen. For example, with the\n", "array {1, 2, 2, 2, 5, 2}, either all three 2\u02bcs in the middle must be chosen or\n", "not, all as a group. (one loop can be used to find the extent of the identical\n", "values).\n", "\n", "groupSumClump(0, [2, 4, 8], 10) \u2192 true\n", "groupSumClump(0, [1, 2, 4, 8, 1], 14) \u2192 true\n", "groupSumClump(0, [2, 4, 4, 8], 14) \u2192 false\n", "*/\n", "\n", "bool groupSumClump(int start, vector<int> nums, int target) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"groupSumClump(0, [2, 4, 8], 10) \u2192 true\", groupSumClump(0, {2, 4, 8}, 10), true );\n", "printTest( \"groupSumClump(0, [1, 2, 4, 8, 1], 14) \u2192 true\", groupSumClump(0, {1, 2, 4, 8, 1}, 14), true );\n", "printTest( \"groupSumClump(0, [2, 4, 4, 8], 14) \u2192 false\", groupSumClump(0, {2, 4, 4, 8}, 14), false );\n", "printTest( \"groupSumClump(0, [8, 2, 2, 1], 9) \u2192 true\", groupSumClump(0, {8, 2, 2, 1}, 9), true );\n", "printTest( \"groupSumClump(0, [8, 2, 2, 1], 11) \u2192 false\", groupSumClump(0, {8, 2, 2, 1}, 11), false );\n", "printTest( \"groupSumClump(0, [1], 1) \u2192 true\", groupSumClump(0, {1}, 1), true );\n", "printTest( \"groupSumClump(0, [9], 1) \u2192 false\", groupSumClump(0, {9}, 1), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > splitArray"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to divide the ints into two groups, so\n", "that the sums of the two groups are the same. Every int must be in one group or\n", "the other. Write a recursive helper method that takes whatever arguments you\n", "like, and make the initial call to your recursive helper from splitArray(). (No\n", "loops needed.)\n", "\n", "splitArray([2, 2]) \u2192 true\n", "splitArray([2, 3]) \u2192 false\n", "splitArray([5, 2, 3]) \u2192 true\n", "*/\n", "\n", "bool splitArray(vector<int> nums) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"splitArray([2, 2]) \u2192 true\", splitArray({2, 2}), true );\n", "printTest( \"splitArray([2, 3]) \u2192 false\", splitArray({2, 3}), false );\n", "printTest( \"splitArray([5, 2, 3]) \u2192 true\", splitArray({5, 2, 3}), true );\n", "printTest( \"splitArray([5, 2, 2]) \u2192 false\", splitArray({5, 2, 2}), false );\n", "printTest( \"splitArray([1, 1, 1, 1, 1, 1]) \u2192 true\", splitArray({1, 1, 1, 1, 1, 1}), true );\n", "printTest( \"splitArray([1, 1, 1, 1, 1]) \u2192 false\", splitArray({1, 1, 1, 1, 1}), false );\n", "printTest( \"splitArray([]) \u2192 true\", splitArray({}), true );\n", "printTest( \"splitArray([1]) \u2192 false\", splitArray({1}), false );\n", "printTest( \"splitArray([3, 5]) \u2192 false\", splitArray({3, 5}), false );\n", "printTest( \"splitArray([5, 3, 2]) \u2192 true\", splitArray({5, 3, 2}), true );\n", "printTest( \"splitArray([2, 2, 10, 10, 1, 1]) \u2192 true\", splitArray({2, 2, 10, 10, 1, 1}), true );\n", "printTest( \"splitArray([1, 2, 2, 10, 10, 1, 1]) \u2192 false\", splitArray({1, 2, 2, 10, 10, 1, 1}), false );\n", "printTest( \"splitArray([1, 2, 3, 10, 10, 1, 1]) \u2192 true\", splitArray({1, 2, 3, 10, 10, 1, 1}), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > splitOdd10"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to divide the ints into two groups, so\n", "that the sum of one group is a multiple of 10, and the sum of the other group is\n", "odd. Every int must be in one group or the other. Write a recursive helper\n", "method that takes whatever arguments you like, and make the initial call to your\n", "recursive helper from splitOdd10(). (No loops needed.)\n", "\n", "splitOdd10([5, 5, 5]) \u2192 true\n", "splitOdd10([5, 5, 6]) \u2192 false\n", "splitOdd10([5, 5, 6, 1]) \u2192 true\n", "*/\n", "\n", "bool splitOdd10(vector<int> nums) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"splitOdd10([5, 5, 5]) \u2192 true\", splitOdd10({5, 5, 5}), true );\n", "printTest( \"splitOdd10([5, 5, 6]) \u2192 false\", splitOdd10({5, 5, 6}), false );\n", "printTest( \"splitOdd10([5, 5, 6, 1]) \u2192 true\", splitOdd10({5, 5, 6, 1}), true );\n", "printTest( \"splitOdd10([6, 5, 5, 1]) \u2192 true\", splitOdd10({6, 5, 5, 1}), true );\n", "printTest( \"splitOdd10([6, 5, 5, 1, 10]) \u2192 true\", splitOdd10({6, 5, 5, 1, 10}), true );\n", "printTest( \"splitOdd10([6, 5, 5, 5, 1]) \u2192 false\", splitOdd10({6, 5, 5, 5, 1}), false );\n", "printTest( \"splitOdd10([1]) \u2192 true\", splitOdd10({1}), true );\n", "printTest( \"splitOdd10([]) \u2192 false\", splitOdd10({}), false );\n", "printTest( \"splitOdd10([10, 7, 5, 5]) \u2192 true\", splitOdd10({10, 7, 5, 5}), true );\n", "printTest( \"splitOdd10([10, 0, 5, 5]) \u2192 false\", splitOdd10({10, 0, 5, 5}), false );\n", "printTest( \"splitOdd10([10, 7, 5, 5, 2]) \u2192 true\", splitOdd10({10, 7, 5, 5, 2}), true );\n", "printTest( \"splitOdd10([10, 7, 5, 5, 1]) \u2192 false\", splitOdd10({10, 7, 5, 5, 1}), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Recursion-2 > split53"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of ints, is it possible to divide the ints into two groups, so\n", "that the sum of the two groups is the same, with these constraints: all the\n", "values that are multiple of 5 must be in one group, and all the values that are\n", "a multiple of 3 (and not a multiple of 5) must be in the other. (No loops\n", "needed.)\n", "\n", "split53([1, 1]) \u2192 true\n", "split53([1, 1, 1]) \u2192 false\n", "split53([2, 4, 2]) \u2192 true\n", "*/\n", "\n", "bool split53(vector<int> nums) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"split53([1, 1]) \u2192 true\", split53({1, 1}), true );\n", "printTest( \"split53([1, 1, 1]) \u2192 false\", split53({1, 1, 1}), false );\n", "printTest( \"split53([2, 4, 2]) \u2192 true\", split53({2, 4, 2}), true );\n", "printTest( \"split53([2, 2, 2, 1]) \u2192 false\", split53({2, 2, 2, 1}), false );\n", "printTest( \"split53([3, 3, 5, 1]) \u2192 true\", split53({3, 3, 5, 1}), true );\n", "printTest( \"split53([3, 5, 8]) \u2192 false\", split53({3, 5, 8}), false );\n", "printTest( \"split53([2, 4, 6]) \u2192 true\", split53({2, 4, 6}), true );\n", "printTest( \"split53([3, 5, 6, 10, 3, 3]) \u2192 true\", split53({3, 5, 6, 10, 3, 3}), true );"]}
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}