java - 总和为给定数字的子集计数(允许重复)。没有得到正确的输出

Question

Input: 4
       1 3 5 7
       8

Output: 6

这段代码有什么问题？
它类似于子集求和问题。这里唯一的区别是我们有无限的数组元素供应。
我的输出:
7 1
7 1
5 3
5 3
5 1 1 1
5 3
5 3
5 1 1 1
3 3 1 1
3 3 1 1
3 1 1 1 1 1
3 1 1 1 1 1
1 1 1 1 1 1 1 1
13
我正在打印代码正在计算的所有组合以供引用。某些组合会打印两次或三次。我应该做哪些改变来跳过重复的组合？

import java.util.*;
public class denomination {
    public static int result=0;
    public static void count(int n, int[] arr, int sum, Stack<Integer> out){
        if(sum<0 || n<=0){
            return;
        }
        if(sum==0){
            result++;
            for (int x : out)
                System.out.print(x + " ");
            System.out.println();
            return;
        }
        out.push(arr[n-1]);
        count(n, arr, sum-arr[n-1], out);
        count(n-1, arr, sum-arr[n-1],out);
        if(!out.empty())
            out.pop();
        count(n-1, arr, sum, out);
    }
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = in.nextInt();
        int sum = in.nextInt();
        Stack<Integer> out = new Stack<Integer>();
        count(n, arr, sum, out);
        System.out.println(result);
    }
}

Answer 1

请注意 1,7和 7,1都是相同的子集，总和为 8。
我们可以将子集表示为 Map<Integer, Integer>在哪里:

key - 来自 arr 的元素.

值(value) - 使用次数。

使用这种表示方式， 1,7和 7,1将表示为 Map = {1:1, 7:1} ( key 不在 Map 中排序)。
我们可以在 Set<Map<Integer, Integer>> 中存储唯一的子集.
现在编码很简单:

public class Demo {
    public static void count(int[] arr, int targetSum, Map<Integer, Integer> currMap, Set<Map<Integer, Integer>> subsets) {
        if (targetSum > 0) { 
            for (int integer : arr) {
                Map<Integer, Integer> newMap = new HashMap<>(currMap);
                Integer integerUseCount = currMap.getOrDefault(integer, 0);
                newMap.put(integer, integerUseCount + 1);

                count(arr, targetSum - integer, newMap, subsets); // "Let's try with this"
            }
        } else if (targetSum == 0) { // We found a subset
            subsets.add(currMap);
        }
    }

    public static void main(String[] args) {
        Set<Map<Integer, Integer>> subsets = new HashSet<>();
        count(new int[]{1, 3, 5, 7}, 8, new HashMap<>(), subsets);
        System.out.println("Output: "+ subsets.size());
        System.out.println("Subsets are:");
        subsets.forEach(System.out::println);
    }
}

输出:

Output: 6
Subsets are:
{1=2, 3=2}
{1=5, 3=1}
{1=3, 5=1}
{1=1, 7=1}
{5=1, 3=1}
{1=8}