求和到给定数量的子集的计数(允许重复).没有得到正确的输出

Question

Input: 4
1 3 5 7
8

Output: 6

这个代码怎么了？

它类似于子集和问题。这里唯一的区别是我们有无限的数组元素。我的输出：
7 1
71
5 3
5 3
5 1 1 1
53
51 1 1
3 3 1 1
3 1 1 1 1 1
3 1 1 11 1 1 1<1 1 1 1 11
1 1 1 11 11 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>，其中：

• arr中的关键元素
• 值-使用次数

使用此表示，1,7和7,1都将表示为Map={1:1, 7:1}(密钥在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}