CODEWITHSUNDEEP
algorithmdynamic-programmingsubsetsubset-sum
coder hacker
coder hacker

Reputation: 4868

Variation of subset sum

Given an array of numbers I want to find out set of numbers whose sum is a multiple of Given number.

I know this is variation of subset sum. But the problem is that there are infinite multiples of a number. So I can't think of a Dynamic Problem Solution to the problem.

So how to extend subset sum problem to it?

Upvotes: 1

Views: 1196

Answers (3)

DDM
DDM

Reputation: 1

Here is code for finding the number of ways you can calculate the sum value.

public static void main(String[] args) {

    Scanner scan=new Scanner(System.in);
    int n=scan.nextInt();//number of elements in the set
    int m=scan.nextInt();//sum needs to be calculated
    scan.nextLine();

    int[] setValue=new int[m];
    long[][] setSplit=new long[m+1][n+1];
    for(int i=0;i<m; i++)
        {
        setValue[i]=scan.nextInt();
    }
    setSplit[0][0]=1;
    //when sum is 0
    for(int i=1; i<m+1; i++)
        {
        setSplit[i][0]=1;
    }
    //when sum is more than 0 but set element is 0
    for(int j=1; j<n+1; j++)
            {
            setSplit[0][j]=0;
        }
    int temp=0;
    for(int i=1; i<=m; i++)
        {

        for(int j=1; j<n+1; j++)
            {
            setSplit[i][j]=setSplit[i-1][j];
            if(j>=setValue[i-1])
                {     

                setSplit[i][j]=setSplit[i][j]+setSplit[i][j-setValue[i-1]];

            }
        }

    }
   // System.out.println(Arrays.deepToString(setSplit));

    System.out.println(setSplit[m][n]);/*this will give number of ways sum can be calculated*/ 
}

Upvotes: 0

shebang
shebang

Reputation: 413

Pseudo polynomial DP solution to subset sum uses the DP state:

DP(n, s) = Number of ways of getting a sum of s using first n elements of the set

And takes O(ns) time. If I want to find all the multiples of d, I am only interested in remainders of subset sums with d. Remember modulo is distributive. Therefore, I change the DP state to

DP(n, m) = Number of subsets whose sum = m mod d using the first n elements

Space reduced to O(nd) and time also O(nd) One convention followed in the actual pseudopolynomial solution is to traverse the DP array from the end, allowing you ro use only O(s) space. That cannot be done here. The best you can do is to use O(2m) memory to store previous and current DP arrays.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372814

Although there are infinitely many multiples of every (nonzero) number, there are only finitely many multiples of a number that will be less than the sum of all the elements in your set. In other words, you can always upper-bound the maximum multiple that could be generated by the sum of the elements of the set. This should enable you to use standard pseudopolynomial-time DP techniques to solve the problem.

Hope this helps!

Upvotes: 0

Related Questions