698. Partition to K Equal Sum Subsets

題目網址：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/

題意：給一整數 array nums 和一正整數 k, 返回是否能把 nums 拆分成 k 的非空 subset, 且每個 subset 元素總和皆相等。

注意：nums.length ≤ 16

Solution 1：

想法：總共有 n 顆球、k 個桶子, 以「球」為視角, 每顆球都有 k 個桶子可以選擇, 每個桶子的容量為 target = sum / k。

e.g. nums = [1, 2, 2, 4, 3, 3], k = 3

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum % k != 0) { // 無法分成 k 個相同的 subset
            return false;
        }

        const int target = sum / k;
        vector<int> buckets(k, target);

        // nums 由大到小排序, 大的先做有利於剪枝
        sort(nums.begin(), nums.end(), greater());

        return dfs(nums, 0, nums.size(), buckets, k);
    }

private:
    bool dfs(vector<int>& nums, int i, int n, vector<int>& buckets, int& k){
        // 代表 n 顆球都能放入桶內, 不需用 for loop 檢查每個桶是否為 0
        // 因為前面已經判斷過 (sum % k) 是否為 0
        // 所以只要 n 顆球都能放入桶內, 每個桶之元素和必為 target
        if (i == n) {
            return true;
        }

        // 每顆球都有 k 個選擇
        for (int j = 0; j < k; ++j) {
            if (nums[i] > buckets[j]) { // buckets[i] 剩餘容量不足, 則跳過
                continue;
            }

            // 如果當前桶和上一個桶內的元素和相等, 則跳過
            // 因為當前這顆球放在當前桶和上一個桶都是一樣的, 對後面的球如何擺放沒有影響
            if (j > 0 && buckets[j - 1] == buckets[j]) { // 剪枝
                continue;
            }

            buckets[j] -= nums[i]; // 將球放入桶中

            // 遞迴窮舉下一顆球的所有情況, 返回是否能將所有球放入桶中
            if (dfs(nums, i + 1, n, buckets, k)) {
                return true;
            }

            buckets[j] += nums[i]; // 若不行, 則撤銷, 往下一個桶嘗試
        }

        return false; // nums[i] 無法放入任何桶
    }
};

• time：$O(k^n)$ ➔ 每個顆都有 k 個桶子可以選擇桶子, 所以組合出的結果為 $k^n$ 種
• space：$O(n)$ ➔ 取決於遞迴深度, stack 中每一層代表第 i 顆球選擇哪個桶子, 總共 n 層

Solution 2：（TLE 無法通過）

想法：總共有 n 顆球、k 個桶子, 以「桶子」為視角（每個桶子都會遍歷所有球）, 每顆球有 2 種選擇（選 or 不選）, 每個桶子都有 $O(2^n)$ 種選擇。

e.g. nums = [1, 2, 2, 4, 3, 3], k = 3

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum % k != 0) { // 無法分成 k 個相同的 subset
            return false;
        }

        const int target = sum / k;
        vector<int> buckets(k, target);
        vector<bool> used(nums.size(), false); // 紀錄第 i 顆球是否已被使用

        return dfs(nums, used, 0, buckets, k - 1); // 從最後一個桶開始放球
    }

private:
    bool dfs(vector<int>& nums, vector<bool>& used, int i, vector<int>& buckets, int k){
        // 因為前面已經判斷過 (sum % k) 是否為 0
        // 若 k - 1 個桶子已放滿, 則剩下的球之和必為 target, 必能放入最後一個桶
        if (k == 0) return {
            true;
        }

        // buckets[k] 已被填滿, 故從下一個桶子開始放（i 設 0 是因為下一桶要遍歷所有球）
        if (buckets[k] == 0) {
            return dfs(nums, used, 0, buckets, k - 1);
        }

        for (int j = i; j < nums.size(); ++j) {
            // 球已放入別的桶子 or 當前桶的容量不足, 則跳過
            if (used[j] || nums[j] > buckets[k]) {
                continue;
            }

            // 將球放入當前桶
            buckets[k] -= nums[j];
            used[j] = true; // 將球標記為已用過

             // 遞迴窮舉下一顆球的所有情況, 下一顆球仍是從第 k 個桶開始放
            if (dfs(nums, used, j + 1, buckets, k)) {
                return true;
            }

            // 將球從當前桶取出
            buckets[k] += nums[j];
            used[j] = false; // 將球標記為未使用過
        }

        return false; // buckets[k] 無法放入任何球
    }
};

• time：$O(k \cdot 2^n)$
  • 每個桶要遍歷 n 顆球, 每顆球都有 2 種選擇(選 or 不選), 所以組合的結果有 $2^n$ 種
  • 總共有 k 個桶, 故為 $O(k \cdot 2^n)$
• space：$O(k \cdot n)$ ➔ 取決於遞迴深度, 每個桶子最多有 n 次選擇（n 層）, 總共 k 個桶, 故為 $O(k \cdot n)$

Solution 3：

想法：改進 Solution 2, 之所以會 TLE 是因為會重複計算, 必須儲存已使用球的狀態來進行剪枝

• 剪枝
  • used array 可以認為一 backtracking 過程中的狀態。可以用一個 memo 來記錄每種情況的 used 返回 true 或 false。如果當前的 used 狀態是曾經出現過的, 那就不用再繼續窮舉了
  • 根據題目給的 nums.length ≤ 16, 所以我們可以用「狀態壓縮」的技巧, 用 int 類型的 used 來替代 used array, 其中 used 中最右邊的編號為 0（e.g. used = 3 = 00...0011, 代表 nums[0] 和 nums[1] 已被使用）
  • 為了方便查找, 我們利用 hash map 來記錄每一種 used 狀態返回的是 true 還是 false

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum % k != 0) { // 無法分成 k 個相同的 subset
            return false;
        }

        const int target = sum / k;
        vector<int> buckets(k, target);
        int used = 0;  // 紀錄每個數字是否被拜訪過

        return dfs(nums, used, 0, buckets, k - 1); // 從最後一個桶開始放球
    }

private:
    unordered_map<int, bool> memo; // memo 儲存每一種 used 狀態

    bool dfs(vector<int>& nums, int& used, int i, vector<int>& buckets, int k){
        // 因為前面已經判斷過 (sum % k) 是否為 0
        // 若 k - 1 個桶子已放滿, 則剩下的球之和必為 target, 必能放入最後一個桶
        if (k == 0) {
            return true;
        }

        // buckets[k] 已被填滿, 故從下一個桶子開始放, 且必須儲存球的狀態
        if (buckets[k] == 0) {
            const bool res = dfs(nums, used, 0, buckets, k - 1);
            memo[used] = res;
            return res;
        }

        // 如果出現過 used 這種情況, 則直接返回結果
        if (memo.find(used) != memo.end()) {
            return memo[used];
        }

        for (int j = i; j < nums.size(); ++j) {
            if (((used >> j) & 1) == 1) { // 球已放入別的桶子, 則跳過
                continue;
            }

            if (nums[j] > buckets[k]) { // 當前桶的容量不足, 則跳過
                continue;
            }

            // 將球放入當前桶
            buckets[k] -= nums[j];
            used |= (1 << j); // 用 OR 將球標記為已用過

             // 遞迴窮舉下一顆球的所有情況, 下一顆球仍是從第 k 個桶開始放
            if (dfs(nums, used, j + 1, buckets, k)) {
                return true;
            }

            // 將球從當前桶取出
            buckets[k] += nums[j];
            used ^= (1 << j); // 用 XOR 將球標記為未使用過
        }

        return false; // buckets[k] 無法放入任何球
    }
};

• time：$O(k \cdot 2^n)$
  • 每個桶要遍歷 n 顆球, 每顆球都有 2 種選擇(選 or 不選), 所以組合的結果有 $2^n$ 種
  • 總共有 k 個桶, 故為 $O(k \cdot 2^n)$
• space：$O(2^n)$ ➔ memo 最大長度為 $2^n$, 因為最多 $2^n$ 種狀態