数组分解K个等和子数组

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

vector<bool> tri;
vector<int> number;
int K;
bool result=false;

//des 目标值   countK 当前值
void dfs(int index,int des,int countI,int countD){
    
    if(countD==des){
        countI++;
        if(countI==K){
            result=true;
            return;
        }
        int nindex=-1;
        for(int i=0;i<tri.size();i++){
            if(!tri[i]){
                nindex=i;
                break;
            }
        }
        if(nindex==-1)
            return ;
        tri[nindex]=1;
        dfs(nindex,des,countI,number[nindex]);
        tri[nindex]=0;
    }
    if(countD<des&&index<number.size()&&!tri[index+1]){
        tri[index+1]=1;
        //选择index+1
        dfs(index+1,des,countI,countD+number[index+1]);
        tri[index+1]=0;
        
        //未选择index+1
        dfs(index+1,des,countI,countD);
    }
}

void funS(string s){
    istringstream is(s);
    char ts;
    int ti;
    while (is>>ts) {
        if (ts==']') {
            is>>ts;
            is>>ti;
            K=ti;
            break;
        }
        is>>ti;
        number.push_back(ti);
    }
    sort(number.begin(), number.end());
    tri.resize(number.size(),0);
}

void getNum(){
    int he=0;
    for (int i=0; i<number.size(); i++) {
        he+=number[i];
    }
    if(he%K)
        return;
    else{
        tri[0]=1;
        dfs(0,he/K,0,number[0]);
    }
}

int main(){
    string als;
    getline(cin, als);
    funS(als);
    getNum();
    if(result){
        cout<<"True"<<endl;
    }else{
        cout<<"False"<<endl;
    }
}

import sys
 
 
def find_value(num, value):
    for idx, data in enumerate(num):
        if data<=value:
            num = num[:idx] + num[idx+1:]
            return value-data, num, True
    return value, num, False
 
def check_num(num, k):
    if k==1:
        return True
    num_sum = int(sum(num))
    mean_value = int(num_sum/k)
    if not (mean_value*k % num_sum == 0):
        return False
     
    value = mean_value
    while len(num)>0:
        value, num,rtn = find_value(num, value)
        #rtn, num = sub_list(num, mean_value)
        if not rtn:
            return False
        if value == 0:
            value = mean_value
    return True
 
 
if __name__=="__main__":
    line = sys.stdin.readline().strip()
    num_str, k = line.split(";")
    num = eval(num_str)
    num = [int(data) for data in num]
    k = int(k)
    print(check_num(num, k))

class Solution: def canPartitionKSubsets(self, nums: 'List[int]', k: 'int') -> 'bool': if k == 1: return True sum_num = sum(nums) if sum_num % k != 0: return False avg = sum_num // k
        nums.sort(reverse=True)
        n = len(nums) if n < k :return False visited = set() def dfs(k,tmp_sum,loc): if tmp_sum == avg: # print(visited) return dfs(k-1,0,0) if k == 1: return True for i in range(loc,n): if i not in visited and nums[i] + tmp_sum <= avg:
                    visited.add(i) if dfs(k,tmp_sum+nums[i],i+1): return True visited.remove(i) return False return dfs(k,0,0)