java子集和数问题回溯法算法_子集和数问题——回溯法

子集和数问题是指给定一个集合，从中选出若干个元素，使它们的和等于一个给定的数。回溯法是一种解决这个问题的常见算法。

具体的解决方法是：首先定义一个数组来存储选择的结果，假设这个数组叫做solution。然后从集合的第一个元素开始，尝试将它加入solution中，如果加入后solution中的元素和仍然小于等于给定的数，那么就继续向下递归，否则就回溯到上一层。当所有的元素都尝试过之后，就得到了所有可能的解。

以下是Java代码实现：

public void subsetSum(int[] set, int sum) {
    int[] solution = new int[set.length];
    subsetSum(set, solution, 0, sum, 0);
}

private void subsetSum(int[] set, int[] solution, int pos, int sum, int curSum) {
    if (curSum == sum) {
        // 找到了一个解
        for (int i = 0; i < pos; i++) {
            System.out.print(solution[i] + " ");
        }
        System.out.println();
        return;
    }
    if (curSum > sum || pos == set.length) {
        // 回溯到上一层
        return;
    }
    // 尝试将下一个元素加入solution中
    solution[pos] = set[pos];
    subsetSum(set, solution, pos + 1, sum, curSum + set[pos]);
    // 不选择当前元素
    solution[pos] = 0;
    subsetSum(set, solution, pos + 1, sum, curSum);
}

在这个代码中，我们使用了一个pos来表示当前选择的元素在集合中的位置，curSum表示当前已经选择的元素的和。回溯的过程就是在不断地向上返回，并将solution数组中的元素设为0。