动态规划-打印具有给定和的所有子集

Question

我正在练习一些动态规划问题，并试图解决用给定的和打印所有子集的问题。例如：对于集：{1,2,3,4,5}和总和值=10，我应该得到以下结果：

[1, 2, 3, 4]
[1, 4, 5]
[2, 3, 5]

我在不使用表的情况下得到了所需的结果，我使用表来防止重复调用相同的表和求和。但是，当使用表时，我在输出中没有得到[2，3，5]。

    private static void printSubsetsWithSum(int i, int arr[], int sum, List<Integer> list, int j, boolean[][] table, Map<String,Integer> map) {
        if(sum == 0) {
            System.out.println(list);
        } else if(sum < 0 || i >= arr.length) {
            return;
        } else if(table[i][sum]) {
            return ;
        } else if(arr[i] > sum) {
            printSubsetsWithSum(i+1, arr, sum, list, j, table, map);
            table[i][sum] = true;
            map.put( sum + "_" + i + "_" + arr[i], map.getOrDefault(sum + "_" + i + "_" + arr[i], 0) + 1);
        } else {
            list.add(arr[i]);
            printSubsetsWithSum(i+1, arr, sum-arr[i], list, j+1, table, map);
            list.remove(j);
            printSubsetsWithSum(i+1, arr, sum, list, j, table, map);
            map.put( sum + "_" + i + "_" + arr[i], map.getOrDefault(sum + "_" + i + "_" + arr[i], 0) + 1);
            table[i][sum] = true;
        }
    }

    public static void printSubsetsWithSum(int sum, int[] arr) {
        boolean table[][] = new boolean[arr.length][sum+1];
        Map<String,Integer> map = new LinkedHashMap<String,Integer>();
        printSubsetsWithSum(0, arr, sum, new ArrayList<>(), 0, table, map);
        System.out.println(map);
    }

    public static void main(String[] args) {
        printSubsetsWithSum(10, new int[] {1,2,3,4,5});
    }

请帮忙！

Answer 1

private static void printSubsetsWithSum(int i, int arr[], int sum, List<Integer> list, int j, boolean[][] table, Map<String,Integer> map) {
    if(sum == 0) {
        System.out.println(list);
    } else if(sum < 0 || i >= arr.length) {
        return;
    } else if(table[i][sum]) {
        return ;
    } else if(arr[i] > sum) {
        printSubsetsWithSum(i+1, arr, sum, list, j, table, map);
        table[i][sum] = true;
        map.put( sum + "_" + i + "_" + arr[i], map.getOrDefault(sum + "_" + i + "_" + arr[i], 0) + 1);
    } else {
        list.add(arr[i]);
        printSubsetsWithSum(i+1, arr, sum-arr[i], list, j+1, table, map);
        list.remove(j);
        printSubsetsWithSum(i+1, arr, sum, list, j, table, map);
        map.put( sum + "_" + i + "_" + arr[i], map.getOrDefault(sum + "_" + i + "_" + arr[i], 0) + 1);
        table[i][sum] = true;// <<---- remove this line it works
    }
}

该行将表[4][5]标记为true，i=4，list=[2，3]sum=5将匹配表[i][sum==true