CODEWITHSUNDEEP
javaarraysalgorithm
user1529540
user1529540

Reputation:

Checking whether there is a subset of size k of an array which has a sum multiple of n

Good evening, I have an array in java with n integer numbers. I want to check if there is a subset of size k of the entries that satisfies the condition:

The sum of those k entries is a multiple of m.

How may I do this as efficiently as possible? There are n!/k!(n-k)! subsets that I need to check.

Upvotes: 0

Views: 508

Answers (3)

mostruash
mostruash

Reputation: 4189

If numbers have lower and upper bounds, it might be better to:

  1. Iterate all multiples of n where lower_bound * k < multiple < upper_bound * k
  2. Check if there is a subset with sum multiple in the array (see Subset Sum problem) using dynamic programming.

Complexity is O(k^2 * (lower_bound + upper_bound)^2). This approach can be optimized further, I believe with careful thinking.

Otherwise you can find all subsets of size k. Complexity is O(n!). Using backtracking (pseudocode-ish):

function find_subsets(array, k, index, current_subset):
  if current_subset.size = k:
    add current_subset to your solutions list
    return

  if index = array.size:
    return

  number := array[index]
  add number to current_subset
  find_subsets(array, k, index + 1, current_subset)
  remove number from current_subset
  find_subsets(array, k, index + 1, current_subset)

Upvotes: 0

Matt
Matt

Reputation: 5684

I don't like this solution, but it may work for your needs

public boolean containsSubset( int[] a , int currentIndex, int currentSum, int depth, int divsor, int maxDepth){

    //you could make a, maxDepth, and divisor static as well


    //If maxDepthis equal to depth, then our subset has k elements, in addition the sum of
    //elements must be divisible by out divsor, m
    //If this condition is satisafied, then there exists a subset of size k whose sum is divisible by m
    if(depth==maxDepth&&currentSum%divsor==0) 
         return true;

    //If the depth is greater than or equal maxDepth, our subset has more than k elements, thus
    //adding more elements can not satisfy the necessary conditions
    //additionally we know that if it contains k elements and is divisible by m, it would've satisafied the above condition. 
    if(depth>=maxdepth)
         return false;


    //boolean to be returned, initialized to false because we have not found any sets yet
    boolean ret = false;

    //iterate through all remaining elements of our array 
    for (int i = currentIndex+1; i < a.length; i++){
    //this may be an optimization or this line
    //for (int i = currentIndex+1; i < a.length-maxDepth+depth; i++){



         //by recursing, we add a[i] to our set we then use an or operation on all our subsets that could 
         //be constructed from the numbers we have so far so that if any of them satisfy our condition (return true) 
         //then the value of the variable ret will be true
         ret |= containsSubset(a,i,currentSum+a[i],depth+1,divisor, maxDepth);

    } //end for


    //return the variable storing whether any sets of numbers that could be constructed from the numbers so far.
    return ret;

}

Then invoke this method as such

 //this invokes our method with "no numbers added to our subset so far" so it will try adding 
 // all combinations of other elements to determine if the condition is satisfied.
 boolean answer = containsSubset(myArray,-1,0,0,m,k);

EDIT:

You could probably optimize this by taking everything modulo (%) m and deleting repeats. For examples with large values of n and/or k, but small values of m, this could be a pretty big optimization.

EDIT 2:

The above optimization I listed isn't helpful. You may need the repeats to get the correct information. My bad.

Happy Coding! Let me know if you have any questions!

Upvotes: 0

kraskevich
kraskevich

Reputation: 18556

You can use dynamic programming. The state is (prefix length, sum modulo m, number of elements in a subset). Transitions are obvious: we either add one more number(increasing the number of elements in a subset and computing new sum modulo m), or we just increase prefix lenght(not adding the current number). If you just need a yes/no answer, you can store only the last layer of values and apply bit optimizations to compute transitions faster. The time complexity is O(n * m * k), or about n * m * k / 64 operations with bit optimizations. The space complexity is O(m * k). It looks feasible for a few thousands of elements. By bit optimizations I mean using things like bitset in C++ that can perform an operation on a group of bits at the same time using bitwise operations.

Upvotes: 1

Related Questions