# 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();

}

Last modified 3yr ago