如何使用Java递归求解带连续索引约束的子集和问题

你提出的新增prevSelected标记参数的思路完全可行，索引连续的要求本质是限制选元素的规则：一旦在连续选元素的过程中跳过某个元素，就不能再把后续元素加入当前连续段；如果当前没在构建连续段，可以选择跳过元素，或者以当前元素为起点开启新的连续段。

递归状态设计 #

递归函数需要传入4个核心参数：

• 原数组arr
• 当前遍历到的索引index
• 剩余需要凑的目标和remaining
• 布尔标记prevSelected：标识上一个索引位置的元素是否被纳入当前连续子集

递归终止条件 #

• 当remaining == 0时，说明已经找到符合要求的连续子集，返回true
• 当index == arr.length时，说明遍历完所有元素仍未凑出目标和，返回false

核心分支逻辑 #

递归分支按照prevSelected的取值分为两类：

1. prevSelected = true（上一个元素已被选入当前连续段）

   • 选择当前元素：连续规则不被破坏，递归进入下一层时传入remaining - arr[index]、prevSelected = true、索引+1
   • 不选当前元素：当前连续段直接终止，递归进入下一层时传入remaining不变、prevSelected = false、索引+1
     注意：该场景下不存在「跳过当前元素再选后续元素」的选项，会直接破坏索引连续要求

2. prevSelected = false（上一个元素未被选中，当前没有正在构建的连续段）

   • 选择当前元素：以当前元素为起点开启新的连续段，递归进入下一层时传入remaining - arr[index]、prevSelected = true、索引+1
   • 不选当前元素：继续跳过，递归进入下一层时传入remaining不变、prevSelected = false、索引+1

初始调用规则 #

初始状态下还没有选中任何元素，相当于索引-1的虚拟位置元素未被选中，因此入口调用参数为dfs(arr, 0, targetSum, false)。

Java代码实现 #

public class ContinuousSubsetSum {
    public static boolean checkContinuousSubsetSum(int[] arr, int target) {
        return dfs(arr, 0, target, false);
    }

    private static boolean dfs(int[] arr, int index, int remaining, boolean prevSelected) {
        // 命中目标和
        if (remaining == 0) {
            return true;
        }
        // 遍历完数组未命中
        if (index == arr.length) {
            return false;
        }

        boolean result = false;
        if (prevSelected) {
            // 上一个元素选中的分支
            result = result || dfs(arr, index + 1, remaining - arr[index], true);
            result = result || dfs(arr, index + 1, remaining, false);
        } else {
            // 上一个元素未选中的分支
            result = result || dfs(arr, index + 1, remaining - arr[index], true);
            result = result || dfs(arr, index + 1, remaining, false);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] testArr = {1,2,3,4};
        System.out.println(checkContinuousSubsetSum(testArr, 5)); // 输出true，2+3为连续子集
        System.out.println(checkContinuousSubsetSum(testArr, 8)); // 输出false，不存在和为8的连续子集
    }
}

补充说明：上述实现默认空集属于合法子集（即target为0时直接返回true），如果题目要求子集非空，只需要在终止条件处增加「是否选中过元素」的判断即可。

内容的提问来源于stack exchange，提问作者Dani