Diving Board

16.11 Diving Board: You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

• Not the most efficient, but we can build a B-tree that expands out to represent the possible combinations given k planks (building k levels in the process.

• Each node will represent the accumulative length until we get to the leafs. Our final result will be the values of our leafs in the tree.

• The reason this isn't entirely efficient is because we will obtain so overlap in the sum of the values (2+3) = (3+2), but our tree distinct them as different.

  • The larger the k, the more overlaps.

• Optimized: With only two possibilities and k levels. The unique combinations made are simple:

  • Ex. len1 = 3, len2 = 4, k = 4

    • Produces unique sums that are reflected by: its key combination:

      • 2222 = 8

      • 2223 = 9

      • 2233 = 10

      • 2333 = 11

      • 3333 = 12

vector<int> build_k_planks(int k, int length1, int length2) {
    vector<int> comb (k);
    vector<vector<int>> combs;
    combs.reserve(k + 1);

    fill(comb.begin(), comb.end(), length1);
    combs.push_back(comb);

    // now modify this vector
    for (int i = 0; i < k; i++) {
        comb[i] = length2;
        combs.push_back(comb);
    }

    comb.clear();
    // now return sum
    for (auto i : combs) {
        int sum = accumulate(i.begin(), i.end(), 0);
        comb.push_back(sum);
    }
    return comb;
}

int main() {
    vector<int> sums = build_k_planks(4, 2, 3);
    for (auto i : sums) cout << i << " "; cout << endl;
    pause();

    sums = build_k_planks(10, 45, 21);
    for (auto i : sums) cout << i << " "; cout << endl;
    pause();
}