698. Partition to K Equal Sum Subsets 数组分成和相同的k组

［抄题］：

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into knon-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

dfs中的cc是：组数k直接等于1

dfs的退出条件是：cur_sum == target

［思维问题］：

不懂“是否”题为啥要用dfs：这一步能不能、下一步能不能，每个元素都要算到，所以用boolean DFS

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

DFS扩展的依据是：下一步没有访问过 visited = f，就设置visited = t &回溯。中间不要直接return，否则后面没法做。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

dfs的target直接写成target就行了，就是个参数

［二刷］：

dfs的start直接写成start就行了，就是个参数 traverse中要变成i + 1

［三刷］：

找到k组之后，继续找k - 1 组，变量变化之后就要控制它的最后值是否为0或1 了

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

有变量k的次数递减，就必须写退出条件。DFS最重要的反而是退出条件

［复杂度］：Time complexity: O(n) Space complexity: O()

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        
        //ini: get sum
        for (int num : nums) sum += num;
        int[] visited = new int[nums.length];
        
        //cc: k == 1
        if (k == 1) return true;
        if (k <= 0 || sum % k != 0) return false;
        
        //canPartition
        return canPartition(0, nums, visited, 0, k, sum / k);
    }
    
    public boolean canPartition(int start, int[] nums, int[] visited, int curSum, int k, int target) {
        if(k==1) return true;
        
        //exit :curSum == target
        if (curSum == target) return canPartition(0, nums, visited, 0, k - 1, target);
        
        //backtracing
        for (int i = start; i < nums.length; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                //do not return directly
                if(canPartition(i + 1, nums, visited, curSum + nums[i], k, target)) return true;
                visited[i] = 0;
            }
        }
        
        return false;
    }
}

View Code

698. Partition to K Equal Sum Subsets 数组分成和相同的k组

相关推荐