CODEWITHSUNDEEP
algorithm
user3840069
user3840069

Reputation: 765

Efficient way to count subsets with given sum

Given N numbers I need to count subsets whose sum is S.

Note : Numbers in array need not to be distinct.

My current code is :

int countSubsets(vector<int> numbers,int sum)
{
    vector<int> DP(sum+1);
    DP[0]=1;
    int currentSum=0;
    for(int i=0;i<numbers.size();i++)
    {
        currentSum+=numbers[i];
        for (int j=min(sum,currentSum);j>=numbers[i];j--)
            DP[j]+=DP[j - numbers[i]];
    }
    return DP[sum];
}

Can their be any efficient way than this ?

Constraints are : 

1 ≤ N ≤ 14
1 ≤ S ≤ 100000
1 ≤ A[i] ≤ 10000

Also their are 100 test cases in a single file. So please help if their exist better solution than this one

Upvotes: 2

Views: 693

Answers (2)

kraskevich
kraskevich

Reputation: 18546

You can use the fact that N is small: it is possible to generate all possible subsets of the given array and check if its sum is S for each of them. The time complexity is O(N * 2 ** N) or O(2 ** N)(it depends on the way of the generation). This solution should be fast enough for the given constraints.

Here is a pseudo code of an O(2 ** N) solution:

result = 0

void generate(int curPos, int curSum):
     if curPos == N:
         if curSum == S:
             result++
         return
     // Do not take the current element.
     generate(curPos + 1, curSum)
     // Take it.
     generate(curPos + 1, curSum + numbers[curPos])

generate(0, 0)

A faster solution based on the meet in the middle technique:

  1. Let's generate all subsets for the first half of the array using the algorithm described above and put their sums into a map(which maps a sum to the number of subsets that have it. It can be either a hash table or just an array because S is relatively small). This step takes O(2 ** (N / 2)) time.

  2. Now let's generate all subsets for the second half and for each of them add the number of subset that sum up to S - currentSum e in the first half(using the map constructed in 1.), where the currentSum is the sum of all elements in the current subseta. Again, we have O(2 ** (N / 2)) subsets and each of them is processed in O(1).

The total time complexity is O(2 ** (N / 2)).

A pseudo code for this solution:

Map<int, int> count = new HashMap<int, int>() // or an array of size S + 1.
result = 0

void generate1(int[] numbers, int pos, int currentSum):
    if pos == numbers.length:
        count[currentSum]++
        return
    generate1(numbers, pos + 1, currentSum)
    generate1(numbers, pos + 1, currentSum + numbers[pos])

void generate2(int[] numbers, int pos, int currentSum):
    if pos == numbers.length:
        result += count[S - currentSum]
        return
    generate2(numbers, pos + 1, currentSum)
    generate2(numbers, pos + 1, currentSum + numbers[pos])

generate1(the first half of numbers, 0, 0)
generate2(the second half of numbers, 0, 0)

If N is odd, the middle element can go to either the first half or to the second one. It doesn't matter where it goes as long as it goes to exactly one of them.

Upvotes: 0

fex
fex

Reputation: 3558

N is small (2^20 - is about 1 milion - 2^14 is really small value) - just iterate over all subsets, below I wrote pretty fast way to do that (bithacking). Treat integers as sets (that's enumerating subsets in Lexicographical order)

int length = array.Length;
int subsetCount = 0;
for (int i=0; i<(1<<length); ++i)
{
    int currentSet = i;
    int tempIndex = length-1;
    int currentSum = 0;

    while (currentSet > 0) // iterate over bits "from the right side"
    {
       if (currentSet & 1 == 1) // if current bit is "1"
          currentSum += array[tempIndex];

       currentSet >>= 1;
       tempIndex--;        
    }
    subsetCount += (currentSum == targetSum) ? 1 : 0;
}

Upvotes: 1

Related Questions