find k-partition of a graph that satisfies the condition

Question

Given the adjacency matrix of a graph, I want to divide the nodes into k partitions where [the sum of edges inside each part] minus [the sum of edges between these k parts] is the maximum.

Here is my attempt:

I made all partitions of the nodes and looked up for partitions including k subsets. Then calculated all of the edges inside each part considering all pairs of nodes and I did this for edges between all pairs of parts too and looked for the maximum. The problem is that my approach is not efficient in terms of time and memory. So I am looking for a faster method. I know that I shouldn’t store all partitions in memory and have to do the calculations while generating each one. But I don’t know how to implement this.

Any help is appreciated.