子集和问题详解（Java实现动态规划与回溯算法）

方法一：回溯算法（暴力搜索）

回溯法通过递归尝试每一种可能的组合。对于数组中的每个元素，我们有两个选择：选或不选。这种“二叉决策树”的方式可以穷举所有子集。

public class SubsetSumBacktrack {    public static boolean canPartition(int[] nums, int target) {        // 边界情况处理        if (target == 0) return true;        if (nums == null || nums.length == 0) return false;        return backtrack(nums, target, 0);    }    private static boolean backtrack(int[] nums, int remaining, int index) {        // 找到解        if (remaining == 0) {            return true;        }        // 超出范围或剩余和为负        if (index >= nums.length || remaining < 0) {            return false;        }        // 选择当前元素        boolean include = backtrack(nums, remaining - nums[index], index + 1);        // 不选择当前元素        boolean exclude = backtrack(nums, remaining, index + 1);        return include || exclude;    }    // 测试示例    public static void main(String[] args) {        int[] nums = {3, 34, 4, 12, 5, 2};        int target = 9;        System.out.println(canPartition(nums, target)); // 输出 true    }}

这种方法虽然直观，但时间复杂度为 O(2ⁿ)，当数组较大时效率很低。因此，我们引入更高效的动态规划解法。

方法二：动态规划（推荐）

动态规划的核心思想是“记忆化”——避免重复计算。我们定义一个布尔型二维数组 dp[i][j]，表示前 i 个元素是否能组成和为 j 的子集。

状态转移方程如下：

• dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]

其中：

• dp[i-1][j] 表示不选第 i 个元素
• dp[i-1][j - nums[i-1]] 表示选第 i 个元素（前提是 j ≥ nums[i-1]）

public class SubsetSumDP {    public static boolean canPartition(int[] nums, int target) {        if (target == 0) return true;        if (nums == null || nums.length == 0) return false;        int n = nums.length;        // 创建 DP 表        boolean[][] dp = new boolean[n + 1][target + 1];        // 初始化：和为 0 总是可以达成（空子集）        for (int i = 0; i <= n; i++) {            dp[i][0] = true;        }        // 填充 DP 表        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= target; j++) {                // 不选当前元素                dp[i][j] = dp[i - 1][j];                // 如果可以选，尝试选                if (j >= nums[i - 1]) {                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];                }            }        }        return dp[n][target];    }    // 测试示例    public static void main(String[] args) {        int[] nums = {3, 34, 4, 12, 5, 2};        int target = 9;        System.out.println(canPartition(nums, target)); // 输出 true    }}

动态规划的时间复杂度为 O(n × target)，空间复杂度也可通过滚动数组优化至 O(target)。这是解决子集和问题最常用且高效的方法。

总结

通过本教程，你已经掌握了使用 Java算法 解决子集和问题的两种核心思路：

• 回溯算法：适合小规模数据，逻辑清晰但效率低；
• 动态规划：适合中等规模数据，时间效率高，是工业级推荐方案。

无论你是准备面试还是学习动态规划和回溯算法，子集和问题都是不可跳过的经典题型。动手敲一遍代码，加深理解吧！