# All Construct

Updated: 01 February 2024

# Problem

This problem is very similar to the previous question but now instead of counting the ways we can construct a string we want to return the the list of ways that the word can be constructed

# Base Implementation

The implementation of this is pretty similar to the Count Construct problem but we return the list of combinations that make the input string

dynamic-programming/memoization/all-construct.ts
export const allConstruct = (target: string, parts: string[]): string[][] => {
// for the base case there is one way to return the combination and that is the empty solution;
if (target == "") return [[]];

let permutations: string[][] = [];

for (let part of parts) {
if (target.startsWith(part)) {
const restOfWord = target.slice(part.length);

const current = allConstruct(restOfWord, parts);
const joint = current.map((arr) => [part, ...arr]);
permutations = [...permutations, ...joint];
}
}

return permutations;
};


The complexity of this is the same as the Can Construct implementation with a time complexity $O(n^m)$ and space complexity of $O(n^m)$ since we always need to return a large list of subarrays of combinations

# With memoization

We implement the memoization as in the previous examples

dynamic-programming/memoization/all-construct-memo.ts
type Memo = Record<string, string[][]>;

export const allConstruct = (
target: string,
parts: string[],
memo: Memo = {}
): string[][] => {
if (target in memo) return memo[target];

// for the base case there is one way to return the combination and that is the empty solution;
if (target == "") return [[]];

let permutations: string[][] = [];

for (let part of parts) {
if (target.startsWith(part)) {
const restOfWord = target.slice(part.length);

const current = allConstruct(restOfWord, parts, memo);
const joint = current.map((arr) => [part, ...arr]);
permutations = [...permutations, ...joint];
}
}

memo[target] = permutations;
return permutations;
};


The complexity of this is the same as the Can Construct memoized implementation with a time complexity $O(n * m^2)$ and space complexity of $O(m^2)$