Dada una matriz de números enteros y un entero positivo k, averigüe si es posible dividir esta matriz en k subconjuntos no vacíos cuyas sumas sean todas iguales.
Ejemplo 1:
Entrada: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Salida: Verdadero
Explicación: Es posible dividirlo en 4 subconjuntos (5), (1, 4), (2,3), (2,3) con sumas iguales.
Solución Java
La solución más sencilla a este problema es DFS. Intentamos colocar cada elemento en uno de los cubos. La siguiente es una solución de Java y hay un diagrama para mostrar la ejecución del método helper () usando el ejemplo dado. Tenga en cuenta la mejora en el bucle for.
public boolean canPartitionKSubsets(int[] nums, int k) { int sum = 0; for(int num: nums){ sum+=num; } if(sum%k!=0){ return false; } int share = sum/k; //sort array Arrays.sort(nums); int j=nums.length-1; if(nums[j]>share){ return false; } while(j>=0 && nums[j]==share){ j--; k--; } int[] buckets = new int[k]; return helper(j, nums, share, buckets); } //put jth number to each bucket and recursively search public boolean helper(int j, int[] nums, int share, int[] buckets){ if(j<0){ return true; } for(int i=0; i<buckets.length; i++){ if(buckets[i]+nums[j]<=share){ buckets[i]+=nums[j]; if(helper(j-1, nums, share, buckets)){ return true; } buckets[i]-=nums[j]; } if(buckets[i]==0) break;// } return false; } |
