使用Java求解排除指定数后总和为目标值的所有非负整数组合

问题说明 #

我们需要求解符合以下条件的所有非负整数组合：

• 组合长度固定为n个非负整数
• 所有元素相加总和等于给定目标值
• 可选排除指定数字集合，所有元素不能属于该集合

实现思路 #

采用回溯法逐位填充组合数值，每一步做合法性校验：

1. 当前选择的数值不在排除集合中
2. 剩余待分配的总和足够分给剩下的空位置（至少每个位置留0）
3. 填充完所有位置后，若总和刚好等于目标值则加入结果集

完整实现代码 #

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

public class StarsBarsSolver {

    public List<List<Integer>> generateCombinations(int count, int targetSum, Set<Integer> excludedNums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), count, targetSum, 0, excludedNums);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int count, int remainSum, int index, Set<Integer> excludedNums) {
        // 已经填充完所有位置
        if (index == count) {
            if (remainSum == 0) {
                result.add(new ArrayList<>(current));
            }
            return;
        }
        // 剪枝：剩余总和为负直接返回
        if (remainSum < 0) {
            return;
        }
        // 当前位置可以选0到remainSum之间的所有数，排除指定集合的数值
        for (int i = 0; i <= remainSum; i++) {
            if (excludedNums.contains(i)) {
                continue;
            }
            current.add(i);
            backtrack(result, current, count, remainSum - i, index + 1, excludedNums);
            current.remove(current.size() - 1);
        }
    }

    // 测试示例
    public static void main(String[] args) {
        StarsBarsSolver solver = new StarsBarsSolver();
        // 需求：3个非负整数和为3，无排除数字
        List<List<Integer>> res = solver.generateCombinations(3, 3, Set.of());
        // 格式化输出
        for (List<Integer> item : res) {
            System.out.printf("(%d,%d,%d) ", item.get(0), item.get(1), item.get(2));
        }
    }
}

测试输出 #

运行上述main方法后，输出结果和示例完全一致：
(0,0,3) (0,1,2) (0,2,1) (0,3,0) (1,0,2) (1,1,1) (1,2,0) (2,0,1) (2,1,0) (3,0,0)

如果需要排除指定数字，比如要排除所有值为1的元素，调用方法时传入Set.of(1)即可，结果会自动过滤不符合要求的组合。

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