Leetcode 2518. Number of Great Partitions

[Woodyiiiiiii]

这道题是周赛第四题，我并没有什么思路。

我一开始的想法是用DFS找到选中数之和大于等于k的组合，很显然这样超过时间复杂度了，因为是O(2^n)。

class Solution {
    int ans = 0;

    final int MOD = 1000000007;

    public int countPartitions(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        boolean[] visited = new boolean[nums.length];

        for (int i = 0; i < nums.length; ++i) {
            visited[i] = true;
            dfs(nums, visited, i, nums[i], sum, k);
            visited[i] = false;
        }

        return ans;
    }

    private void dfs(int[] nums, boolean[] visited, int start, int curSum, int sum, int k) {
        if (curSum >= k && sum - curSum >= k) {
            ans++;
            ans %= MOD;
        }

        for (int i = start + 1; i < nums.length; ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            dfs(nums, visited, i,curSum + nums[i], sum, k);
            visited[i] = false;
        }
    }
}

那有什么方法，能够在O(nlgn)及以下的时间复杂度中找到满足条件的个数呢？

因为正向思维中找到大于等于k的这个条件太大了，行不通，我们不妨用反向思维，找到小于k的组合，然后用总组合相减。

首先观察用例，可以知道总组合的计算条件是2^(n-1)，或者说是2^n-2，因为n太大了，会爆栈超过integer的限制，所以我们用循环，每次*2后取%。顺便用long计算下和值，做一下先决判断。

接着，问题变成如何取数计算和小于k的subsequence的个数了。这里自然地想到coin change II题目的变型。coin change II题目中，因为硬币可以取无限个，所以是在coin循环里面从小到大，而这题是只能取一次，所以循环里从大到小。

这实际上是个 Knapsack(背包) 问题。

class Solution {
    public int countPartitions(int[] nums, int k) {
        final int MOD = (int) (1e9 + 7);
        //        int ans = (int) (Math.pow(2, n) - 2); // exceed integer limit
        int ans = 1;
        long total = 0;
        for (int j : nums) {
            ans = ans * 2 % MOD;
            total += j;
        }
        ans -= 2;
        if (total < 2L * k) return 0;

        long[] dp = new long[k];
        dp[0] = 1L;
        for (int num : nums) {
            for (int i = k - 1; i - num >= 0; --i) {
                dp[i] = (dp[i] + dp[i - num]) % MOD;
            }
        }

        for (int i = 1; i < k; ++i) {
            ans -= dp[i] * 2;
            ans = (ans % MOD + MOD) % MOD;
        }
        return ans;
    }
}

最后，循环DP数组，减去2*dp[i]即可。

注意这里还有一个细节，以为要在减后取余，因为会出现a-b<-MOD的情况，所以减法的取余是((a-b)%MOD+MOD)%MOD。正常情况下如果在[-MOD,MOD]区间内就不用这么麻烦了。所以要弄清楚这个公式的由来。

可以看出，hard难度的题目其实是思维转换+medium难度算法的结合。

tips:

1. 第二次刷的时候，发现先处理判断total<2*k还有另一层深意：避免重复计算。比如初始条件为[1,3,4]和5，dp[4]为2，但其实这两种情况是同一种。所以为了避免这种情况，另一个集合的和要保证大于k。
2. 不要用BigInteger了，尝试了下感觉没意义
3. 三刷，其实观察大小，可以发现答案时间复杂度跟n和k有关，可以猜测是O(nk)

---

• https://leetcode.com/problems/number-of-great-partitions/submissions/871132476/
• https://leetcode.com/problems/coin-change-ii/
• https://leetcode.com/problems/number-of-great-partitions/solutions/2948009/java-c-python-knapsack-problem/?orderBy=hot