139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

• Input: s = "leetcode", wordDict = ["leet", "code"]
• Output: true
• Explanation: Return true because "leetcode" can be segmented as "leet code".

Solution Overview

This problem is reminiscent of backtracking problems like Palindrome Partitioning, where we enumerate all possible segmentations of a string. Here, we check if each substring exists in the dictionary. A backtracking solution in C++ is shown below:

class Solution {
private:
    bool backtracking(const string& s, const unordered_set<string>& wordSet, int start) {
        if (start >= s.size()) return true;
        for (int i = start; i < s.size(); i++) {
            string sub = s.substr(start, i - start + 1);
            if (wordSet.count(sub) && backtracking(s, wordSet, i + 1)) {
                return true;
            }
        }
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return backtracking(s, dict, 0);
    }
};

Knapsack Approach

We can model the problem as a complete knapsack problem: words are items, the string s is the knapsack, and we ask if items can exactly fill the knapsack, allowing unlimited reuse of each item.

Dynamic programming formulation:

1. dp[i]: weather the prefix of length i of s can be segmented. dp[0] = true (empty string is considered segmentable).
2. Transition: dp[i] = true if there exists a j < i such that dp[j] == true and the substring s[j:i] (inclusive from j to i-1) is in the dictionary.
3. Traversal order: Since the order of words matters (we are looking for a specific sequence of words), we treat this as a permutation problem. For complete knapsack permutations, we iterate over the knapsack capacity (outer loop) and then over items (inner loop).

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {               // traverse knapsack capacity
            for (int j = 0; j < i; j++) {                   // traverse items (split point)
                string word = s.substr(j, i - j);
                if (dict.count(word) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

Multiple Knapsack Problem

In the multiple knapsack problem, there are N types of items, each with a maximum quantity M[i], weight C[i], and value W[i]. The goal is to select items to maximize total value without exceeding the knapsack capacity V.

A straightforward approach is to expand each type into individual items (unfold the quantities). This transforms the problem into a standard 0/1 knapsack.

Example:

Item	Weight	Value	Quantity
0	1	15	2
1	3	20	3
2	4	30	2

After expansion, we have six items, each with quantity 1.

Implementation (unfolding):

void testMultipleKnapsack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int capacity = 10;

    // Unfold items
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) {
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }

    // 0/1 knapsack on unfolded items
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < weight.size(); i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[capacity] << endl;
}

Alternative (nested loops for quantity):

void testMultipleKnapsack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int capacity = 10;

    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < weight.size(); i++) {                // traverse item types
        for (int j = capacity; j >= weight[i]; j--) {        // traverse capacity (0/1 knapsack style)
            for (int k = 1; k <= nums[i] && j - k * weight[i] >= 0; k++) {  // traverse quantity
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }
    cout << dp[capacity] << endl;
}

Note: Both methods have the same time complexity O(N * V * K), where N is number of item types, V is knapsack capacity, and K is the average quantity. Binary optimization can reduce the complexity, but the core idea remains similar to unfolding into 0/1 knapsack.

Summary of Knapsack Patterns

Recurrence Formulas

Problem Type	Formula	Example Problems
Can the knapsack be exactly filled (or max weight)	dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])	Partition Equal Subset Sum, Last Stone Weight II
Number of ways to fill exactly	dp[j] += dp[j - nums[i]]	Target Sum, Coin Change 2, Combination Sum IV, Climbing Stairs (complete knapsack version)
Maximum value when filled	dp[j] = max(dp[j], dp[j - weight[i]] + value[i])	Ones and Zeroes
Minimum number of items to fill	dp[j] = min(dp[j - coins[i]] + 1, dp[j])	Coin Change, Perpect Squares

Traversal Order

• 0/1 Knapsack (1D dp): Outer loop over items, inner loop oveer capacity descending.
• Complete Knapsack:
  • If order of items does not matter (combinations): outer loop over items, inner loop over capacity ascending.
  • If order matters (permutations): outer loop over capacity, inner loop over items.
  • For minimizing number of items: either order works.

The key challenge in knapsack problems is often determining the correct traversal order, which determines whether we count combinations or permutations.