【力扣 leetcode】698：划分为k个相等的子集

迷南。 2023-10-09 14:46 23阅读 0赞

## 每日进步 ##

*  **剪枝：** 通过判断避免一些不必要的遍历过程。
    
     *  **可行性剪枝：** 方案不可行时，回溯。
     *  **最优性剪枝:** 方案的解不可能优于当前最优解时，回溯。

## 题目 ##

给定一个整数数组 `nums` 和一个正整数 `k`，找出是否有可能把这个数组分成 `k` 个非空子集，其总和都相等。

*  示例 1：
    
     *  输入： `nums = [4, 3, 2, 3, 5, 2, 1]`，`k = 4`
     *  输出： `True`
     *  说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 *  示例 2:
    
     *  输入: `nums = [1,2,3,4]`，`k = 3`
     *  输出: `false`
 *  提示：
    
     *  `1 <= k <= len(nums) <= 16`
     *  `0 < nums[i] < 10000`
     *  每个元素的频率在 \[1,4\] 范围内

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets  
> 著作权归领扣网络所有。本文仅供个人学习，非商用。

## 题解 ##

采用**深度优先遍历**和**剪枝**的思想，使用**贪心**的策略。

class Solution {
        
        int[] solu_nums;
        int solu_k, len, key;
    
        public boolean canPartitionKSubsets(int[] nums, int k) {
        
            solu_nums = nums;
            solu_k = k;
            len = nums.length;
    
            int sum = 0;
            for (int num : nums){
        
                sum += num;
            }
            if (sum % k != 0)
                return false;
            key = sum / k;
            Arrays.sort(solu_nums);
    
            boolean[] visited = new boolean[len];
            Arrays.fill(visited, false);
    
            boolean ans = dfs(len-1, 0, 0, visited);
            return ans;
        }
    
        public boolean dfs(int idx, int cal, int times, boolean visited[]){
        
            if (times == solu_k)
                return true;
            if (cal == key)
                return dfs(len-1, 0, times+1, visited);
            
            for (int i = idx; i >= 0; i--){
        
                if (visited[i] == true || cal + solu_nums[i] > key)
                    continue;
    
                visited[i] = true;
                boolean ans = dfs(idx-1, cal+solu_nums[i], times, visited);
    
                if (ans)
                    return true;
                else
                    visited[i] = false;
    
                if (cal == 0)
                    return false;
            }
    
            return false;
        }
    }

> 本题的题解参照了这位大佬的思想  
> 链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-ac\_oier-mryw/