Polyglot Notebook (.NET Interactive notebooks) - dynamic programming - helpers

.gitattributes

###############################################################################
# Set default behavior to automatically normalize line endings.
###############################################################################
* text=auto

# Never modify line endings of dib files
*.dib text eol=lf

dotnet.code-workspace

{
	"folders": [
		{
			"path": "."
		}
	],
	"settings": {
		"omnisharp.enableAsyncCompletion": true,
		"omnisharp.useModernNet": true,
		"interactiveWindow.collapseCellInputCode": "always",
		"notebook.showFoldingControls": "always",
		"notebook.cellToolbarVisibility": "hover",
		"notebook.cellFocusIndicator": "border",
		"notebook.diff.ignoreMetadata": false,
		"notebook.diff.ignoreOutputs": true,
		"notebook.dragAndDropEnabled": false,
		"notebook.lineNumbers": "on",
		"notebook.outline.showCodeCells": true,
		"notebook.diff.enablePreview": false,
		"notebook.consolidatedOutputButton": false,
		"notebook.compactView": false,
		"notebook.output.textLineLimit": 50,
		"vsicons.associations.files": [
			{ "icon": "pddl_happenings", "extensions": ["dib"], "format": "svg" }
		],
		"files.exclude": {
			"**/.gitattributes": true,
			"**/.gitignore": true,
			"**/*.code-workspace": true
		}
	},
	"extensions": {
		"recommendations": [
			"vscode-icons-team.vscode-icons",
			"ms-dotnettools.dotnet-interactive-vscode",
		]
	}
}

dynamic-programming-helpers-notebook.dib

#!meta

{"kernelInfo":{"defaultKernelName":null,"items":[{"name":"csharp","languageName":"C#","aliases":["c#","cs"]},{"name":"fsharp","languageName":"F#","aliases":["f#","fs"]},{"name":"pwsh","languageName":"PowerShell","aliases":["powershell"]},{"name":"javascript","languageName":"JavaScript","aliases":["js"]},{"name":"html","languageName":"HTML"},{"name":"sql","languageName":"SQL"},{"name":"kql","languageName":"KQL"},{"name":"mermaid","languageName":"Mermaid"},{"name":"httpRequest","languageName":"http"},{"name":"value"}]}}

#!markdown

# Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

https://www.youtube.com/watch?v=oBt53YbR9Kk

Learn how to use Dynamic Programming in this course for beginners. It can help you solve complex programming problems, such as those often seen in programming interview questions about data structures and algorithms.

This course was developed by Alvin Zablan from Coderbyte. Coderbyte is one of the top websites for technical interview prep and coding challenges.

This course uses images and animations to help you visualize problems and important concepts. After understanding problems conceptually, you will learn how to solve them in JavaScript using Dynamic Programming. Even though JavaScript is used in this course, you will learn concepts and knowledge that you can apply to other programming languages.

## ⭐️ Course Contents ⭐️
- fib memoization
- gridTraveler memoization
- canSum memoization
- howSum memoization
- bestSum memoization
- canConstruct memoization
- countConstruct memoization
- allConstruct memoization
- fib tabulation
- gridTraveler tabulation
- canSum tabulation
- howSum tabulation
- bestSum tabulation
- canConstruct tabulation
- countConstruct tabulation
- allConstruct tabulation

__👇👇👇RUN THIS FIRST👇👇👇__

#!csharp

/* 👈👈👈 ⭐ RUN ME FIRST!!! ⚡Helpers⚡ ⭐*/
using System.Text.Json;

$"Helpers {DateTime.Now}".Display();

public static class Helpers
{
    public static string ArrayToString(IEnumerable<int> nums, int? size = null) {
        size = size ?? nums.Count();
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        sb.Append("[");
        int i = 0;
        foreach(int n in nums) {
            var endToken = (i == (size - 1)) ? string.Empty : ", ";
            sb.AppendFormat("{0}{1}", n, endToken);
            if (++i == size) break;
        }
        sb.Append("]");

        return sb.ToString();
    }

    public static string ArrayToString(IEnumerable<object> obs, int? size = null) {
        if (obs == null) return "<null>";

        size = size ?? obs.Count();
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        sb.Append("[");
        int i = 0;
        foreach(object o in obs) {
            var endToken = (i == (size - 1)) ? string.Empty : ", ";
            sb.AppendFormat("{0}{1}", o == null ? "<null>" : o, endToken);
            if (++i == size) break;
        }
        sb.Append("]");

        return sb.ToString();
    }

    public static string Enumerable2ToString(IEnumerable<IEnumerable<object>> arrOfArr) {
        if (arrOfArr.Count() == 0) {
            return "[]";
        }

        System.Text.StringBuilder sb = new();
        sb.Append("[");
        int count = 0;
        foreach(var arr in arrOfArr) {
            count += arr.Count();
            sb.Append(arr.ToArray().Str()).Append(",");
        }
        if (count == 0) return "[[]]";

        sb.Remove(sb.Length - 1, 1);
        sb.Append("]");
        return sb.ToString();
    }
    
    public static void Log<T>(string funcDefStr, T result, T expected, bool? condition = null) {
        condition = condition ?? EqualityComparer<T>.Default.Equals(result, expected);
        Console.Write($"{funcDefStr} => ");
        Console.Write($"{(result == null ? "<null>" : result)}");
        if (condition == false) {
            Console.Write($" expected: {expected}");
        } else {
            Console.Write(" ✔");
        }
        Console.WriteLine(Asrt.T(condition == true));
    }
}

public static string Str(this IEnumerable<int> arr, int? size = null) {
    return Helpers.ArrayToString(arr, size);
}

public static string Str(this IEnumerable<object> arr, int? size = null) {
    return Helpers.ArrayToString(arr, size);
}

public static string SortNStr(this IEnumerable<int> arr, int? size = null) {
    return Helpers.ArrayToString(arr?.OrderBy(x => x), size);
}

public static string SortNStr(this IEnumerable<object> arr, int? size = null) {
    return Helpers.ArrayToString(arr?.OrderBy(x => x), size);
}

public static string Str2(this IEnumerable<IEnumerable<object>> arrOfArr) {
    return Helpers.Enumerable2ToString(arrOfArr);
}

public static string Str2(this IEnumerable<IEnumerable<int>> arrOfArr) {
    IEnumerable<IEnumerable<object>> objArr = arrOfArr?.Select(x => x.Cast<object>());
    return Helpers.Enumerable2ToString(objArr);
}

public static string Str2(this int[][] arrOfArr) {
    IEnumerable<IEnumerable<object>> objArr = arrOfArr?.Select(x => x.Cast<object>());
    return Helpers.Enumerable2ToString(objArr);
}

public static T FromJson<T>(string json) => Newtonsoft.Json.JsonConvert.DeserializeObject<T>(json);
// alias
public static T J<T>(string json) => FromJson<T>(json);

public static void Log<T>(string funcDefStr, T result, T expected, bool? condition = null) => Helpers.Log(funcDefStr, result, expected, condition);

/* ============================================= ASSERT =============================================*/

public static class Asrt {
    private static bool hasErrors;
    public static string T(bool condition) {
        if (!condition) {
            hasErrors = true;
        }
        return condition ? "" : " | WRONG!!! ❌";
    }

    public static void Flush() {
        if (hasErrors) {
            hasErrors = false;
            Console.WriteLine("\n❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌");
            // throw new System.Data.DataException("Invalid result");
        } else {
            Console.WriteLine("\n✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅");
        }
    }
}

#!markdown

## Fibonacci memoization - no helpers

Write a function `fib(n)` that takes in a number as an argument.
The function should return the `n-th` number of the Fibonacci sequence.

The 0th number of the sequence is 0.
The 1th number of the sequence is 1.

#!csharp

"Fibonacci memoization - no helpers".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
    return -1;
}

(int intput, int output)[] testCases = {
    (7, 13),
    (8, 21),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}

#!csharp

"✅Fibonacci memoization - no helpers".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
    if (n <= 2) return 1;
    if (memo.ContainsKey(n)) return memo[n];

    int result = Fib(n-1, memo) + Fib(n-2, memo);
    memo[n] = result;
    return result;
}

(int intput, int output)[] testCases = {
    (7, 13),
    (8, 21),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}

#!markdown

## Fibonacci memoization

Write a function `fib(n)` that takes in a number as an argument.
The function should return the `n-th` number of the Fibonacci sequence.

The 0th number of the sequence is 0.
The 1th number of the sequence is 1.

#!csharp

"Fibonacci memoization".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
    return -1;
}

(int intput, int output)[] testCases = {
    (6, 8),
    (7, 13),
    (8, 21),
    (45, 1134903170),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Log($"f({input})", result, output);
}
Asrt.Flush();

#!csharp

"✅Fibonacci memoization".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
    if (n <= 2) return 1;
    if (memo.ContainsKey(n)) return memo[n];

    int result = Fib(n-1, memo) + Fib(n-2, memo);
    memo[n] = result;
    return result;
}

(int intput, int output)[] testCases = {
    (6, 8),
    (7, 13),
    (8, 21),
    (45, 1134903170),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Log($"f({input})", result, output);
}
Asrt.Flush();

/*
    TIME:   O(n)
    SPACE:  O(n)
*/

#!markdown

## Grid traveler memoization

Say that you are a traveler on a 2D grid. You begin in the **top-left** corner and your goal is to travel to the **bottom-right** corner. You may only move `down` or `right`.

In how many ways can you travel to the goal on a grid with dimensions **m * n**?

Write a function `gridTraveler(m, n)` that calculate this.

#!csharp

"GridTraveler memoization".Display();

public int GridTraveler(int m, int n, Dictionary<string, int> memo = null) {
    return -1;
}

(int m, int n, int output)[] testCases = {
    (1, 1, 1),
    (2, 3, 3),
    (3, 2, 3),
    (3, 3, 6),
    (17, 17, 601080390)
};

foreach (var (m, n, output) in testCases) {
    var result = GridTraveler(m, n, new Dictionary<string, int>());
    Log($"f({m}, {n})", result, output);
}
Asrt.Flush();

#!csharp

"✅GridTraveler memoization".Display();

public int GridTraveler(int m, int n, Dictionary<string, int> memo) {
    if (m <= 0 || n <= 0) return 0;
    if (m == 1 && n == 1) return 1;
    string key = $"{m}-{n}";
    if (memo.ContainsKey(key)) return memo[key];

    int result = GridTraveler(m - 1, n, memo) + GridTraveler(m, n - 1, memo);
    memo[key] = result;
    return result;
}

(int m, int n, int output)[] testCases = {
    (1, 1, 1),
    (2, 3, 3),
    (3, 2, 3),
    (3, 3, 6),
    (17, 17, 601080390)
};

foreach (var (m, n, output) in testCases) {
    var result = GridTraveler(m, n, new());
    Log($"f({m}, {n})", result, output);
}
Asrt.Flush();

/*
    m * n - possible combinations

    BRUTE FORCE
    TIME:   O(2^(n+m))
    SPACE:  O(n + m)    - stack

    MEMOIZED
    TIME:   O(m*n)
    SPACE:  O(n + m)
*/

#!markdown

## CanSum memoization

Write a function `canSum(targetSum, numbers)` that takes in a `targetSum` and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the `targetSum` using numbers from the array.

#!csharp

"CanSum memoization".Display();

public bool CanSum(int targetSum, int[] numbers, Dictionary<int, bool> memo = null) {
    return false;
}

(int targetSum, int[] numbers, bool output)[] testCases = {
    (7, new int[] { 2,3 }, true),
    (7, new int[] { 5,3,4,7 }, true),
    (7, new int[] { 2,4 }, false),
    (8, new int[] { 2,3,5 }, true),
    (300, new int[] { 7,14 }, false),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = CanSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result, output);
}
Asrt.Flush();

#!csharp

"✅CanSum memoization".Display();

public bool CanSum(int targetSum, int[] numbers, Dictionary<int, bool> memo = null) {
    if (targetSum == 0) return true;
    if (targetSum < 0) return false;
    if (memo.ContainsKey(targetSum)) return memo[targetSum];

    foreach (int n in numbers) {
        int remainder = targetSum - n;

        if (CanSum(remainder, numbers, memo) == true) {
            memo[targetSum] = true;
            return true;
        }
    }

    memo[targetSum] = false;
    return false;
}

(int targetSum, int[] numbers, bool output)[] testCases = {
    (7, new int[] { 2,3 }, true),
    (7, new int[] { 5,3,4,7 }, true),
    (7, new int[] { 2,4 }, false),
    (8, new int[] { 2,3,5 }, true),
    (300, new int[] { 7,14 }, false),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = CanSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result, output);
}
Asrt.Flush();

/*
    m = target sum
    n = array length

    BRUTE FORCE
    TIME:   O(n^m)
    SPACE:  O(m)    - stack

    MEMOIZED
    TIME:   O(m*n)
    SPACE:  O(m)
*/

#!markdown

## HowSum memoization

Write a function `howSum(targetSum, numbers)` that takes in a `targetSum` and an array of numbers as arguments.

The Function should return an array containing any combination of elements that add up to exactly the `targetSum`. If there is no combination that adds up to the `targetSum`, then return null.

#!csharp

"HowSum memoization".Display();

public int[] HowSum(int targetSum, int[] numbers, Dictionary<int, int[]> memo) {
    return null;
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 2,3 }, new int[] { 3,2,2 }),
    (7, new int[] { 5,3,4,7 }, new int[] { 4,3 }),
    (7, new int[] { 2,4 }, null),
    (8, new int[] { 2,3,5 }, new int[] { 2,2,2,2 }),
    (300, new int[] { 7,14 }, null),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.SortNStr(), output?.SortNStr());
}
Asrt.Flush();

#!csharp

"✅HowSum memoization".Display();

public int[] HowSum(int targetSum, int[] numbers, Dictionary<int, int[]> memo) {
    if (targetSum < 0) return null;
    if (targetSum == 0) return new int[0];
    if (memo.ContainsKey(targetSum)) return memo[targetSum];

    foreach (int n in numbers) {
        int remainder = targetSum - n;

        var result = HowSum(remainder, numbers, memo);
        if (result != null) {
            result = result.Append(n).ToArray();
            memo[targetSum] = result;
            return result;
        }
    }

    memo[targetSum] = null;
    return null;
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 2,3 }, new int[] { 3,2,2 }),
    (7, new int[] { 5,3,4,7 }, new int[] { 4,3 }),
    (7, new int[] { 2,4 }, null),
    (8, new int[] { 2,3,5 }, new int[] { 2,2,2,2 }),
    (300, new int[] { 7,14 }, null),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.SortNStr(), output?.SortNStr());
}
Asrt.Flush();

/*
    m = target sum
    n = array length

    BRUTE FORCE
    TIME:   O((n^m) * m)
    SPACE:  O(m)    - stack

    MEMOIZED
    TIME:   O(n*m²)
    SPACE:  O(m²)
*/

#!markdown

## BestSum memoization

Write a function `bestSum(targetSum, numbers)` that takes in a `targetSum` and an array of `numbers` as arguments.

The function should return an array containing the **shortest** combination of numbers that add up to exactly the `targetSum`.

If there is a tie for shortest combination, you may return any one of the shortest.

#!csharp

"BestSum memoization".Display();

public int[] BestSum(int targetSum, int[] numbers, Dictionary<int, int[]> memo) {
    return null;
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 5,3,4,7 }, new int[] { 7 }),
    (8, new int[] { 2,3,5 }, new int[] { 3,5 }),
    (8, new int[] { 1,4,5 }, new int[] { 4,4 }),
    (53, new int[] { 1,2,5,25 }, new int[] { 1,2,25,25 }),
    (100, new int[] { 1,2,5,25 }, new int[] { 25,25,25,25 }),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = BestSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.SortNStr(), output?.SortNStr());
}
Asrt.Flush();

#!csharp

"✅BestSum memoization".Display();

public int[] BestSum(int targetSum, int[] numbers, Dictionary<int, int[]> memo) {
    if (targetSum < 0) return null;
    if (targetSum == 0) return new int[0];
    if (memo.ContainsKey(targetSum)) return memo[targetSum];

    List<int> minCombination = null;

    foreach (int n in numbers) {
        int remainder = targetSum - n;
        int[] remainderCombination = BestSum(remainder, numbers, memo);
        if (remainderCombination != null) {
            List<int> combination = new();
            combination.Add(n);
            combination.AddRange(remainderCombination);
            if (minCombination == null || remainderCombination.Length < minCombination.Count) {
                minCombination = combination;
            }
        }
    }
    memo[targetSum] = minCombination?.ToArray();
    return memo[targetSum];
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 5,3,4,7 }, new int[] { 7 }),
    (8, new int[] { 2,3,5 }, new int[] { 3,5 }),
    (8, new int[] { 1,4,5 }, new int[] { 4,4 }),
    (53, new int[] { 1,2,5,25 }, new int[] { 1,2,25,25 }),
    (100, new int[] { 1,2,5,25 }, new int[] { 25,25,25,25 }),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = BestSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.SortNStr(), output?.SortNStr());
}
Asrt.Flush();

/*
    m = target sum
    n = array length

    BRUTE FORCE
    TIME:   O((n^m) * m)
    SPACE:  O(m²)    - stack

    MEMOIZED
    TIME:   O(n*m²)
    SPACE:  O(m²)
*/

#!markdown

## CanConstruct memoization

Write a function `canConstruct(target, wordBank)` that accepts a target string and an array of strings.

The function should return a boolean indicating whether or not the `target` can be constructed by concatenating elements of the `wordBank` array.

You may reuse elements of `wordBank` as many times as you need.

#!csharp

"CanConstruct memoization".Display();

public bool CanConstruct(string target, string[] wordBank, Dictionary<string, bool> memo) {
    return false;
}

(string target, string[] wordBank, bool output)[] testCases = {
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, true),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, false),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, true),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, false),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CanConstruct(target, wordBank, new());
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

#!csharp

"✅CanConstruct memoization".Display();

public bool CanConstruct(string target, string[] wordBank, Dictionary<string, bool> memo) {
    if (target == string.Empty) return true;
    if (memo.ContainsKey(target)) return memo[target];

    foreach (string word in wordBank) {
        if (target.StartsWith(word)) { //.IndexOf(word) == 0
            string suffix = target.Substring(word.Length);
            if (CanConstruct(suffix, wordBank, memo)) {
                memo[target] = true;
                return true;
            }
        }
    }

    memo[target] = false;
    return false;
}

(string target, string[] wordBank, bool output)[] testCases = {
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, true),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, false),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, true),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, false),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CanConstruct(target, wordBank, new());
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

/*
    m = target sum
    n = array length

    BRUTE FORCE
    TIME:   O((n^m) * m)
    SPACE:  O(m²)    - stack

    MEMOIZED
    TIME:   O(n*m²)
    SPACE:  O(m²)
*/

#!markdown

## CountConstruct memoization

Write a function `countConstruct(target, wordBank)` that accepts a target string and an array of strings.

The function should return the **number of ways** that the `target` can be constructed by concatenating elements of the `wordBank` array.

You may reuse elements of `wordBank` as many times as you need.

#!csharp

"CountConstruct memoization".Display();

public int CountConstruct(string target, string[] wordBank, Dictionary<string, int> memo) {
    return 0;
}

(string target, string[] wordBank, int output)[] testCases = {
    ("purple", new string[] { "purp", "p", "ur", "le", "purpl" }, 2),
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, 1),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, 0),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, 4),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, 0),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CountConstruct(target, wordBank, new());
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

#!csharp

"✅CountConstruct memoization".Display();

public int CountConstruct(string target, string[] wordBank, Dictionary<string, int> memo) {
    if (target == string.Empty) return 1;
    if (memo.ContainsKey(target)) return memo[target];

    int totalCount = 0;
    foreach (string word in wordBank) {
        if (target.StartsWith(word)) {
            string suffix = target.Substring(word.Length);
            int count = CountConstruct(suffix, wordBank, memo); 
            totalCount += count;
        }
    }
    memo[target] = totalCount;
    return totalCount;
}

(string target, string[] wordBank, int output)[] testCases = {
    ("purple", new string[] { "purp", "p", "ur", "le", "purpl" }, 2),
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, 1),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, 0),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, 4),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, 0),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CountConstruct(target, wordBank, new());
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

/*
    m = target.length
    n = array length

    BRUTE FORCE
    TIME:   O((n^m) * m)
    SPACE:  O(m²)    - stack

    MEMOIZED
    TIME:   O(n*m²)
    SPACE:  O(m²)
*/

#!markdown

## AllConstruct memoization

Write a function `allConstruct(target, wordBank)` that accepts a `target` string and an array of strings.

The function should return a 2D array containing **all of the ways** that the `target` can be constructed by concatenating elements of the `wordBank` array. Each element of the 2D array should represent one combination that constructs the `target`.

You may reuse elements of `wordBank` as many times as needed.

#!csharp

"AllConstruct memoization".Display();

public List<List<string>> AllConstruct(string target, string[] wordBank, Dictionary<string, List<List<string>>> memo) {
    List<List<string>> result = new();

    return result;
}

(string target, string[] wordBank, string[][] output)[] testCases = {
    ("purple", FromJson<string[]>("[ 'purp', 'p', 'ur', 'le', 'purpl' ]"), FromJson<string[][]>(@"
     [
        [ 'purp', 'le' ],
        [ 'p', 'ur', 'p', 'le' ],
     ]")),
     ("abcdef", FromJson<string[]>("[ 'ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c' ]"), FromJson<string[][]>(@"
     [
        [ 'ab', 'cd', 'ef' ],
        [ 'ab', 'c', 'def' ],
        [ 'abc', 'def' ],
        [ 'abcd', 'ef' ],
     ]")),
    ("skateboard", FromJson<string[]>(" ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar' ]"), FromJson<string[][]>("[]")),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeef", FromJson<string[]>(" [ 'e', 'ee', 'eee', 'eeee', 'eeeee', 'eeeeee' ]"), FromJson<string[][]>("[]")),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = AllConstruct(target, wordBank, new());
    Log($"f('{target}', '{wordBank.Str()}')", result?.Str2(), output?.Str2());
}
Asrt.Flush();

#!csharp

"✅AllConstruct memoization".Display();

public List<List<string>> AllConstruct(string target, string[] wordBank, Dictionary<string, List<List<string>>> memo) {
    if (target == string.Empty) return new() { new List<string>() };
    if (memo.ContainsKey(target)) return memo[target];

    List<List<string>> result = new();

    foreach (string word in wordBank) {
        if (target.StartsWith(word)) {
            string suffix = target.Substring(word.Length);

            var suffixWays = AllConstruct(suffix, wordBank, memo);

            foreach (var way in suffixWays) {
                List<string> targetWay = new();
                targetWay.Add(word);
                targetWay.AddRange(way);
                result.Add(targetWay);
            }
        }
    }

    memo[target] = result;
    return result;
}

(string target, string[] wordBank, string[][] output)[] testCases = {
    ("purple", FromJson<string[]>("[ 'purp', 'p', 'ur', 'le', 'purpl' ]"), FromJson<string[][]>(@"
     [
        [ 'purp', 'le' ],
        [ 'p', 'ur', 'p', 'le' ],
     ]")),
     ("abcdef", FromJson<string[]>("[ 'ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c' ]"), FromJson<string[][]>(@"
     [
        [ 'ab', 'cd', 'ef' ],
        [ 'ab', 'c', 'def' ],
        [ 'abc', 'def' ],
        [ 'abcd', 'ef' ],
     ]")),
    ("skateboard", FromJson<string[]>(" ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar' ]"), FromJson<string[][]>("[]")),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeef", FromJson<string[]>(" [ 'e', 'ee', 'eee', 'eeee', 'eeeee', 'eeeeee' ]"), FromJson<string[][]>("[]")),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = AllConstruct(target, wordBank, new());
    Log($"f('{target}', '{wordBank.Str()}')", result?.Str2(), output?.Str2());
}
Asrt.Flush();

/*
    m = target.length
    n = array length

    TIME:   O(n^m)
    SPACE:  O(m)
*/

#!markdown

## Fibonacci tabulation

Write a function `fib(n)` that takes in a number as an argument.

The function should return the `n-th` number of the Fibonacci sequence.

- The 0th number of the sequence is 0.
- The 1th number of the sequence is 1.

#!csharp

"Fibonacci tabulation".Display();
public int Fib(int n) {
    // return Fib2Back(n);
    return 0;
}

public int Fib2Back(int n) {
    return 0;
}

(int intput, int output)[] testCases = {
    (6, 8),
    (7, 13),
    (8, 21),
    (40, 102334155),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input);
    Log($"f({input})", result, output);
}
Asrt.Flush();

#!csharp

"✅Fibonacci tabulation".Display();
public int Fib(int n) {
    // return Fib2Back(n);
    int[] dp = new int[n + 1]; // fill with 0 by default;
    dp[1] = 1;
    for (int i = 0; i <= n; i++) {
        int current = dp[i];
        if (i + 1 <= n) dp[i+1] += current;
        if (i + 2 <= n) dp[i+2] += current;
    }
    return dp[n];
}

public int Fib2Back(int n) {
    int[] dp = new int[n + 1]; // fill with 0 by default;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

(int intput, int output)[] testCases = {
    (6, 8),
    (7, 13),
    (8, 21),
    (40, 102334155),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input);
    Log($"f({input})", result, output);
}
Asrt.Flush();

#!markdown

## Grid traveler tabulation

Say that you are a traveler on a 2D grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You may only move down or right.

In how many ways can you travel to the goal on a grid with dimensions m * n?

#!csharp

"GridTraveler tabulation".Display();

public int GridTraveler(int m, int n) {
    return 0;
}

(int m, int n, int output)[] testCases = {
    (1, 1, 1),
    (2, 3, 3),
    (3, 2, 3),
    (3, 3, 6),
    (17, 17, 601080390)
};

foreach (var (m, n, output) in testCases) {
    var result = GridTraveler(m, n);
    Log($"f({m}, {n})", result, output);
}
Asrt.Flush();

#!csharp

"✅GridTraveler tabulation".Display();

public int GridTraveler(int m, int n) {
    int[,] dp = new int[m + 1, n + 1]; // fill with 0 by default, no need to add this

    dp[1,1] = 1;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            int current = dp[i, j];
            if (i + 1 <= m) dp[i+1, j] += current;
            if (j + 1 <= n) dp[i, j+1] += current;
        }
    }

    return dp[m, n];
}

(int m, int n, int output)[] testCases = {
    (1, 1, 1),
    (2, 3, 3),
    (3, 2, 3),
    (3, 3, 6),
    (17, 17, 601080390)
};

foreach (var (m, n, output) in testCases) {
    var result = GridTraveler(m, n);
    Log($"f({m}, {n})", result, output);
}
Asrt.Flush();

#!markdown

## CanSum tabulation

Write a function `canSum(targetSum, numbers)` that takes in a `targetSum` and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the `targetSum` using numbers from the array.

#!csharp

"CanSum tabulation".Display();

public bool CanSum(int targetSum, int[] numbers) {
    return false;
}

(int targetSum, int[] numbers, bool output)[] testCases = {
    (7, new int[] { 2,3 }, true),
    (7, new int[] { 5,3,4,7 }, true),
    (7, new int[] { 2,4 }, false),
    (8, new int[] { 2,3,5 }, true),
    (300, new int[] { 7,14 }, false),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = CanSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result, output);
}
Asrt.Flush();

#!csharp

"✅CanSum tabulation".Display();

public bool CanSum(int targetSum, int[] numbers) {
    bool[] dp = new bool[targetSum + 1]; // fill with false (by default)
    dp[0] = true;
    for (int i = 0; i <= targetSum; i++) {
        if (dp[i] == true) { // very important!!!!
            foreach (int n in numbers) {
                if (i + n <= targetSum) dp[i + n] = true; //dp[i] - current element
            }
        }
    }
    return dp[targetSum];
}

(int targetSum, int[] numbers, bool output)[] testCases = {
    (7, new int[] { 2,3 }, true),
    (7, new int[] { 5,3,4,7 }, true),
    (7, new int[] { 2,4 }, false),
    (8, new int[] { 2,3,5 }, true),
    (300, new int[] { 7,14 }, false),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = CanSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result, output);
}
Asrt.Flush();

/*
    m = targetSum
    n = array length

    TIME:   O(n*m)
    SPACE:  O(m)
*/

#!markdown

## HowSum tabulation

Write a function `howSum(targetSum, numbers)` that takes in a `targetSum` and an array of numbers as arguments.

The Function should return an array containing any combination of elements that add up to exactly the `targetSum`. If there is no combination that adds up to the `targetSum`, then return null.

#!csharp

"HowSum tabulation".Display();

public int[] HowSum(int targetSum, int[] numbers) {
    return new int[0];
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 2,3 }, new int[] { 3,2,2 }),
    (7, new int[] { 5,3,4,7 }, new int[] { 4,3 }),
    (7, new int[] { 2,4 }, null),
    (8, new int[] { 2,3,5 }, new int[] {2,2,2,2 }),
    (300, new int[] { 7,14 }, null),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result?.Str(), output?.Str());
}
Asrt.Flush();

#!csharp

"✅HowSum tabulation".Display();

public int[] HowSum(int targetSum, int[] numbers) {
    int[][] dp = new int[targetSum + 1][];
    dp[0] = new int[0]; //[]

    for (int i = 0; i <= targetSum; i++) {
        if (dp[i] != null) {
            foreach (int n in numbers) {
                if (i + n <= targetSum) {
                    /*
                    int[] currentArray = dp[i];
                    int[] destArr = new int[currentArray.Length + 1];
                    Array.Copy(currentArray, destArr, currentArray.Length);
                    destArr[currentArray.Length] = n;
                    */
                    var list = new List<int>(dp[i].Length + 1);
                    list.AddRange(dp[i]);
                    list.Add(n);
                    dp[i + n] = list.ToArray(); // [ ...d[i], n]
                }
            }
        }
    }

    return dp[targetSum];
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 2,3 }, new int[] { 3,2,2 }),
    (7, new int[] { 5,3,4,7 }, new int[] { 4,3 }),
    (7, new int[] { 2,4 }, null),
    (8, new int[] { 2,3,5 }, new int[] {2,2,2,2 }),
    (300, new int[] { 7,14 }, null),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result?.Str(), output?.Str());
}
Asrt.Flush();

/*
    m = targetSum
    n = array length

    TIME:   O(m²n)
    SPACE:  O(m²)
*/

#!markdown

## BestSum tabulation

Write a function `bestSum(targetSum, numbers)` that takes in a `targetSum` and an array of `numbers` as arguments.

The function should return an array containing the **shortest** combination of numbers that add up to exactly the `targetSum`.

If there is a tie for shortest combination, you may return any one of the shortest.

#!csharp

"BestSum tabulation".Display();

public int[] BestSum(int targetSum, int[] numbers) {
    return new int[0];
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 5,3,4,7 }, new int[] { 7 }),
    (8, new int[] { 2,3,5 }, new int[] { 3,5 }),
    (8, new int[] { 1,4,5 }, new int[] { 4,4 }),
    (100, new int[] { 1,2,5,25 }, new int[] { 25,25,25,25 }),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = BestSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result?.Str(), output?.Str());
}
Asrt.Flush();

#!csharp

"✅BestSum tabulation".Display();

public int[] BestSum(int targetSum, int[] numbers) {
    int[][] dp = new int[targetSum + 1][];
    dp[0] = new int[0];

    for (int i = 0; i <= targetSum; i++) {
        int[] currentElem = dp[i];
        if (currentElem != null) {
            foreach(int n in numbers) {
                if (i + n > targetSum) continue;

                int[] nextElem = dp[i + n];
                int newLength = currentElem.Length + 1;
                if (nextElem == null || nextElem.Length > newLength) {
                    List<int> targetElem = new List<int>(newLength);
                    targetElem.AddRange(currentElem);
                    targetElem.Add(n);
                    dp[i + n] = targetElem.ToArray();
                }
            }
        }
    }

    return dp[targetSum];
}

(int targetSum, int[] numbers, int[] output)[] testCases = {
    (7, new int[] { 5,3,4,7 }, new int[] { 7 }),
    (8, new int[] { 2,3,5 }, new int[] { 3,5 }),
    (8, new int[] { 1,4,5 }, new int[] { 4,4 }),
    (100, new int[] { 1,2,5,25 }, new int[] { 25,25,25,25 }),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = BestSum(targetSum, numbers);
    Log($"f({targetSum}, {numbers.Str()})", result?.Str(), output?.Str());
}
Asrt.Flush();

/*
    m = targetSum
    n = array length

    TIME:   O(m²*n)
    SPACE:  O(m²)
*/

#!markdown

## CanConstruct tabulation

Write a function `canConstruct(target, wordBank)` that accepts a target string and an array of strings.

The function should return a boolean indicating whether or not the `target` can be constructed by concatenating elements of the `wordBank` array.

You may reuse elements of `wordBank` as many times as you need.

#!csharp

"CanConstruct tabulation".Display();

public bool CanConstruct(string target, string[] wordBank) {
    return false;
}

(string target, string[] wordBank, bool output)[] testCases = {
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, true),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, false),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, true),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, false),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CanConstruct(target, wordBank);
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();


/*
    m = target.Length
    n = wordBank.Length

    TIME:   O(m²n) - extra m for substring
    SPACE:  O(m)
*/

#!csharp

"✅CanConstruct tabulation".Display();

public bool CanConstruct(string target, string[] wordBank) {
    int n = target.Length;
    bool[] dp = new bool[n + 1]; // by default fill with 'false'
    dp[0] = true; // can construct empty string (index before 0)
    //dp[1] - can construct 0-1, excluding 1: can construct 'a'
    //dp[2] - can construct 0-2, excluding 2: can construct 'ab': substring(0, 2)

    for (int i = 0; i <= n; i++) {

        if (dp[i] != true) continue;

        foreach (string word in wordBank) {
            if (i + word.Length > n) continue;

            string sub = target.Substring(i, word.Length);
            if (sub == word) {
                dp[i + word.Length] = true;
            }
        }
    }

    // dp.Display();

    return dp[n];
}

(string target, string[] wordBank, bool output)[] testCases = {
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, true),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, false),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, true),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, false),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CanConstruct(target, wordBank);
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

/*
| ⁰ | ¹ | ² | ³ | ⁴ | ⁵ | ⁶ |
|---|---|---|---|---|---|---|
| T | F | T | T | T | F | T |
|---|---|---|---|---|---|---|
| a | b | c | d | e | f |   |
*/
/*
    m = target.Length
    n = wordBank.Length

    TIME:   O(m²n) - extra m for substring
    SPACE:  O(m)
*/

#!markdown

## CountConstruct tabulation

Write a function `countConstruct(target, wordBank)` that accepts a target string and an array of strings.

The function should return the **number of ways** that the `target` can be constructed by concatenating elements of the `wordBank` array.

You may reuse elements of `wordBank` as many times as you need.

#!csharp

"CountConstruct tabulation".Display();

public int CountConstruct(string target, string[] wordBank) {
    return 0;
}

(string target, string[] wordBank, int output)[] testCases = {
    ("purple", new string[] { "purp", "p", "ur", "le", "purpl" }, 2),
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, 1),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, 0),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, 4),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, 0),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CountConstruct(target, wordBank);
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

#!csharp

"✅CountConstruct tabulation".Display();

public int CountConstruct(string target, string[] wordBank) {
    int n = target.Length;
    int[] dp = new int[n + 1];
    dp[0] = 1; // can construct empty string (index before 0)
    //dp[1] - can construct 0-1, excluding 1: can construct 'a'
    //dp[2] - can construct 0-2, excluding 2: can construct 'ab': substring(0, 2)

    for (int i = 0; i<=n; i++) {
        if (dp[i] == 0) continue; // does nothing

        foreach (string word in wordBank) {
            if (i + word.Length > n) continue;

            string sub = target.Substring(i, word.Length);
            if (sub == word) {
                dp[i + word.Length] += dp[i];
            }
        }
    }

    return dp[n];
}

(string target, string[] wordBank, int output)[] testCases = {
    ("purple", new string[] { "purp", "p", "ur", "le", "purpl" }, 2),
    ("abcdef", new string[] { "ab", "abc", "cd", "def", "abcd" }, 1),
    ("skateboard", new string[] { "bo", "rd", "ate", "t", "ska", "sk", "boar" }, 0),
    ("enterapotentpot", new string[] { "a", "p", "ent", "enter", "ot", "o", "t" }, 4),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", new string[] { "e", "ee", "eee", "eeee", "eeeee", "eeeeee" }, 0),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = CountConstruct(target, wordBank);
    Log($"f({target}, {wordBank.Str()})", result, output);
}
Asrt.Flush();

/*
| ⁰ | ¹ | ² | ³ | ⁴ | ⁵ | ⁶ |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 2 | 1 | 2 |
|---|---|---|---|---|---|---|
| p | u | r | p | l | e |   |
*/

/*
    m = target.Length
    n = wordBank.Length

    TIME:   O(m²n) - extra m for substring
    SPACE:  O(m)
*/

#!markdown

## AllConstruct tabulation

Write a function `allConstruct(target, wordBank)` that accepts a `target` string and an array of strings.

The function should return a 2D array containing **all of the ways** that the `target` can be constructed by concatenating elements of the `wordBank` array. Each element of the 2D array should represent one combination that constructs the `target`.

You may reuse elements of `wordBank` as many times as needed.

#!csharp

"AllConstruct tabulation".Display();

public List<List<string>> AllConstruct(string target, string[] wordBank) {
    return new();
}

(string target, string[] wordBank, string[][] output)[] testCases = {
    ("purple", FromJson<string[]>("[ 'purp', 'p', 'ur', 'le', 'purpl' ]"), FromJson<string[][]>(@"
     [
        [ 'purp', 'le' ],
        [ 'p', 'ur', 'p', 'le' ],
     ]")),
     ("abcdef", FromJson<string[]>("[ 'ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c' ]"), FromJson<string[][]>(@"
     [
        [ 'abc', 'def' ],
        [ 'ab', 'c', 'def' ],
        [ 'abcd', 'ef' ],
        [ 'ab', 'cd', 'ef' ],
     ]")),
    ("skateboard", FromJson<string[]>(" ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar' ]"), FromJson<string[][]>("[]")),
    ("eeeeeeeeeeeeeeeeeeeeeef", FromJson<string[]>(" [ 'e', 'ee', 'eee', 'eeee', 'eeeee', 'eeeeee' ]"), FromJson<string[][]>("[]")),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = AllConstruct(target, wordBank);
    Log($"f('{target}', '{wordBank.Str()}')", result?.Str2(), output?.Str2());
}
Asrt.Flush();

/*
    m = target.Length
    n = wordBank.Length

    TIME:   O(n^m) - extra m for substring. EXPONENTIAL
    SPACE:  O(n^m)
*/

#!csharp

"✅AllConstruct tabulation".Display();

public List<List<string>> AllConstruct(string target, string[] wordBank) {
    int n = target.Length;
    List<List<string>>[] dp = new List<List<string>>[n + 1]; // by default filled with null
    dp[0] = new List<List<string>>() { new List<string>() }; // for empty string, empty array: [[]]

    for (int i = 0; i <= n; i++) {
        if (dp[i] == null || dp[i].Count == 0) continue;

        foreach (string word in wordBank) {
            if (i + word.Length > n) continue;
            if (target.Substring(i, word.Length) != word) continue;

            if (dp[i + word.Length] == null) {
                dp[i + word.Length] = new List<List<string>>();
            }

            // copy self (current) into next and add 'word'
            foreach (var curr in dp[i]) {
                var next = new List<string>(curr);
                next.Add(word);
                dp[i + word.Length].Add(next);
            }
        }
    }

    return dp[n] == null ? new List<List<string>>() : dp[n]; //[]
}

(string target, string[] wordBank, string[][] output)[] testCases = {
    ("purple", FromJson<string[]>("[ 'purp', 'p', 'ur', 'le', 'purpl' ]"), FromJson<string[][]>(@"
     [
        [ 'purp', 'le' ],
        [ 'p', 'ur', 'p', 'le' ],
     ]")),
     ("abcdef", FromJson<string[]>("[ 'ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c' ]"), FromJson<string[][]>(@"
     [
        [ 'abc', 'def' ],
        [ 'ab', 'c', 'def' ],
        [ 'abcd', 'ef' ],
        [ 'ab', 'cd', 'ef' ],
     ]")),
    ("skateboard", FromJson<string[]>(" ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar' ]"), FromJson<string[][]>("[]")),
    ("eeeeeeeeeeeeeeeeeeeeeef", FromJson<string[]>(" [ 'e', 'ee', 'eee', 'eeee', 'eeeee', 'eeeeee' ]"), FromJson<string[][]>("[]")),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = AllConstruct(target, wordBank);
    Log($"f('{target}', '{wordBank.Str()}')", result?.Str2(), output?.Str2());
}
Asrt.Flush();

/*
    m = target.Length
    n = wordBank.Length

    TIME:   O(n^m) - extra m for substring. EXPONENTIAL
    SPACE:  O(n^m)
*/