Skip to content
Advertisement

count of subsets which sums upto given number(repetition is allowed). Not getting correct ouput

Input: 4
       1 3 5 7
       8

Output: 6

whats wrong with this code?

It is similar to the sum of subset problem. The only difference here is that we have infinite supplies of array elements. My output:
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
I am printing all combinations that the code is counting for refernce. Some combinations are printed twice or thrice. What changes should I do to skip repeated combinations??

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);
    }
}

Advertisement

Answer

Note that 1,7 and 7,1 are both the same subset that sums to 8.

We can represent the subset as a Map<Integer, Integer> where:

  • Key – element from arr.
  • Value – count of uses.

With this representation, both 1,7 and 7,1 will be represented as the Map= {1:1, 7:1} (keys are not ordered in Map).

We can store unique subsets in Set<Map<Integer, Integer>>.

Now it’s straightforward to code:

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:

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}
Advertisement