整数划分问题java程序

整数划分问题是经典的组合优化问题，它涉及到将一个正整数表示为一系列非负整数的和。在Java中，你可以通过回溯算法来解决这个问题。下面是一个简单的示例：

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

public class IntegerPartition {
    public static List<List<Integer>> integerPartitions(int num) {
        List<List<Integer>> partitions = new ArrayList<>();
        boolean[] used = new boolean[num + 1];
        backtrack(partitions, used, 0, num);
        return partitions;
    }

    private static void backtrack(List<List<Integer>> partitions, boolean[] used, int start, int target) {
        if (target == 0) {
            partitions.add(new ArrayList<>(used)); // 存储当前的子集
            return;
        }
        
        for (int i = start; i <= target; ++i) {
            if (used[i]) continue; // 如果数字已使用过，跳过
            used[i] = true; // 使用当前数字
            backtrack(partitions, used, i, target - i); // 继续寻找剩余部分的划分
            used[i] = false; // 回溯，移除当前数字
        }
    }

    public static void main(String[] args) {
        int num = 4;
        System.out.println("Partitions of " + num + ":");
        for (List<Integer> partition : integerPartitions(num)) {
            System.out.println(partition);
        }
    }
}

在这个程序中，`integerPartitions`函数是主入口，`backtrack`是递归的核心，通过遍历从start到target的所有可能值，并尝试将其添加到当前的子集中。当目标达到0时，就找到了一个有效的划分并存储起来。