LeetCode698划分为k个相等的子集（分支界限法）

题目链接：leetcode698

思路：

• 分支界限法

首先k个子集的长度可以预先计算出来,于是可以用个dfs凑这个长度len。
数组中的每个元素必然属于某个子集，只要全部的元素都能装到对应
每个子集中则必然可以合法地凑出一种合法的k个子集。
- 剪枝
1,当第一个子集枚举最大的元素不能形成合法序列显然全体都不能凑成合法序列，因为这个最大元素显然不能凑到任何一个子集中
2,当前k大的都凑好了显然任何一个较小或者相等的也可以凑好，可以这样想比它大的都可以凑到，小的肯定可以凑到，但我们不需要去考虑它属于哪，因为前提条件我们已经满足剩余的段必然凑到len
3,当某一种方案不能凑给当前子集显然同大小的数也不可能凑给当前子集

Code：

class Solution {
public:
    int n, len;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        n=nums.size();
        vector<bool> vis(n, false);
        sort(nums.begin(), nums.end());
        for(int i=0; i<n; i++) len += nums[i];
        if(len%k!=0) return false;
        len=len/k;
        return dfs(n-1, len, n, nums, vis);
    }
    
    //当前从id位置开始枚举,还有有个sz子集未合法是否能够使所有子集合法
    bool dfs(int id, int cur_len, int sz, vector<int>& arr, vector<bool>& vis) {
        if(sz == 0) return true; //n个数全部装下
        bool isok;
        for(int i=id; i>=0; i--) {
            if(!vis[i] && cur_len>=arr[i]) { //当前的数能够装入当前子集中
                vis[i]=true;
                isok = false;
                if(cur_len == arr[i]) isok = dfs(n-1, len, sz-1, arr, vis); //当前子集已满则要重新找一个len子集
                else isok = dfs(i-1, cur_len-arr[i], sz-1, arr, vis); //当前子集将目前最大的数取了,使得后面的子集更容易凑
                if(isok) return isok; //找到一组合法的拼凑序列
                if(cur_len==0) return isok; //最大的数不能装到任何子集使其形成合法序列
                //否则该数属于其他子集,当前子集不应该取它,进行判重剪枝
                vis[i] = false; //回溯
                while(i>0 && arr[i-1]==arr[i]) i--;
                
            }
        }
        return false;
    }
};