Source: https://leetcode.com/problems/word-break/

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// Brute Force Recursion
// Store all the words in a set for easier lookup and comparison
// If string length is zero, return true
// Loop through from 1 to length of string
// If the substring of 0 to i exists in the set and we recursively check the rest of the string can also be formed, we return true
// Otherwise, if we looped through the whole string
// O(2^N) time because can partition/cut the string in n+1 ways given length n i.e. 2 choices to either break the string at a certain point or continue on
// O(N) space for wordSet and recursion function stack
var wordBreak = function(s, wordDict) {
  const wordSet = new Set(wordDict);
  const wordBreakRec = (str) => {
    if (str.length === 0) {
      return true;
    }
    
    for (let i = 1; i <= str.length; i++) {
      const substring = str.substring(0, i);
      if (wordSet.has(substring) && wordBreakRec(str.substring(i))) {
        return true;
      }
    }
    
    return false;
  };
  
  return wordBreakRec(s);
};