回溯算法找出来最优价格组合

找出所有最佳接近100和等于100的选择

import java.util.ArrayList;
import java.util.List;public class SubsetSum {public static void main(String[] args) {int[] nums = {30, 50, 20,80,100,30,20};List<List<Integer>> result = new ArrayList<>();backtrack(nums, 0, new ArrayList<>(), 0, result);System.out.println("所有组合：");for (List<Integer> combo : result) {System.out.println(combo + " → sum = " + combo.stream().mapToInt(Integer::intValue).sum());}}private static void backtrack(int[] nums, int start, List<Integer> current, int sum, List<List<Integer>> result) {if (sum > 100) return; // 剪枝：超过就不看了if (start == nums.length) {if (!current.isEmpty()) {result.add(new ArrayList<>(current)); // 保存当前组合}return;}// 选择当前元素current.add(nums[start]);backtrack(nums, start + 1, current, sum + nums[start], result);current.remove(current.size() - 1); // 撤销超过的  // 不选当前元素 选择后面的元素进行累加进行计算backtrack(nums, start + 1, current, sum, result);}
}