将M个数分为N组(M>N)，保证N组之间的数之和几乎相等,返回每个组中的数据 java

这是一个NP难问题，可以用回溯法来解决，具体实现如下：

import java.util.ArrayList;
import java.util.List;

public class Partition {
    public static List<List<Integer>> partition(int[] nums, int n) {
        List<List<Integer>> res = new ArrayList<>();
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % n != 0) {
            return res;
        }
        int target = sum / n;
        List<Integer> list = new ArrayList<>();
        int[] used = new int[nums.length];
        dfs(nums, n, 0, 0, target, used, list, res);
        return res;
    }

    private static void dfs(int[] nums, int n, int start, int curSum, int target, int[] used, List<Integer> list, List<List<Integer>> res) {
        if (n == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        if (curSum == target) {
            dfs(nums, n - 1, 0, 0, target, used, list, res);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (used[i] == 0 && curSum + nums[i] <= target) {
                used[i] = 1;
                list.add(nums[i]);
                dfs(nums, n, i + 1, curSum + nums[i], target, used, list, res);
                used[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int n = 3;
        List<List<Integer>> res = partition(nums, n);
        for (List<Integer> list : res) {
            System.out.println(list);
        }
    }
}

这里的思路是先计算出每个组应该得到的数值 target，然后用回溯法来搜索所有的分组方法。在搜索的过程中，需要记录当前已经得到的数值 curSum 和已经使用过的数字 used，然后枚举每个数字是否被使用过，如果没使用过并且加上该数字后不超过 target，则将该数字加入当前组中，并继续递归搜索。搜索结束后，需要将该数字从当前组中移除，以便下一次搜索。