5 Best Ways to Count Subsets that Sum Up to K in Python

Rate this post

πŸ’‘ Problem Formulation: In combinatorial mathematics, a common problem is to find all subsets of a given set of integers whose sum is equal to a specific target number k. Given an array of positive integers, and a target value k, the task is to count the number of subsets whose sum equals k. For example, the input array [1, 2, 3, 4] with k = 5 would yield an output of 2, as the subsets [1,4] and [2,3] sum up to 5.

Method 1: Recursive Approach

A recursive approach to the subset sum problem explores all possible combinations by including or excluding the current element and recursively calling the function to consider the next elements. This method has an exponential time complexity and is not efficient for large inputs.

Here’s an example:

def count_subsets(arr, n, k):
    if k == 0:
        return 1
    if n == 0:
        return 0
    result = count_subsets(arr, n-1, k)
    if arr[n-1] <= k:
        result += count_subsets(arr, n-1, k-arr[n-1])
    return result

# Example Usage
arr = [1, 2, 3, 4]
print(count_subsets(arr, len(arr), 5))

Output: 2

This code snippet defines the function count_subsets which takes three parameters: the array, the length of the array and the target sum k. It counts the number of subsets by adding the count of subsets including the last element to the count of subsets excluding the last element.

Method 2: Dynamic Programming – Memoization

Using memoization, a form of dynamic programming, this method stores the results of overlapping subproblems to avoid unnecessary recalculations, thus improving the efficiency of the recursive approach, especially for larger datasets. This technique involves using a cache to record the results of previous computations.

Here’s an example:

def count_subsets_memo(arr, n, k, memo):
    if k == 0:
        return 1
    if n == 0:
        return 0
    if (n, k) not in memo:
        count_without_n = count_subsets_memo(arr, n - 1, k, memo)
        count_with_n = 0
        if arr[n-1] <= k:
            count_with_n = count_subsets_memo(arr, n - 1, k - arr[n-1], memo)
        memo[(n, k)] = count_with_n + count_without_n
    return memo[(n, k)]

arr = [1, 2, 3, 4]
print(count_subsets_memo(arr, len(arr), 5, {}))

Output: 2

This code snippet uses a helper function count_subsets_memo which includes an additional parameter, a dictionary called memo, that stores intermediate results. This drastically reduces the number of calculations needed for large input arrays.

Method 3: Dynamic Programming – Tabulation

Tabulation is a bottom-up dynamic programming approach that solves the subset sum problem by building a table iteratively and filling it up with the number of subsets that sum up to every possible value up to k. This approach is more space-efficient than naive recursion.

Here’s an example:

def count_subsets_tab(arr, k):
    n = len(arr)
    dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

    # Base case - There's one subset (empty subset) for zero sum
    for i in range(n + 1):
        dp[i][0] = 1
    
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            dp[i][j] = dp[i - 1][j]
            if arr[i - 1] <= j:
                dp[i][j] += dp[i - 1][j - arr[i - 1]]
    
    return dp[n][k]

# Example Usage
arr = [1, 2, 3, 4]
print(count_subsets_tab(arr, 5))

Output: 2

The function count_subsets_tab leverages a two-dimensional array dp to store the number of ways to create sums with subsets. It iteratively computes the results in a tabular format, reducing the need for a recursive stack and improving space complexity.

Method 4: Bitmasking

Bitmasking can be used to generate all possible subsets of an array by representing each subset as a binary number where the presence of an element is marked by a bit 1. This method is efficient for smaller sets since it involves generating all subsets.

Here’s an example:

def count_subsets_bitmask(arr, k):
    n = len(arr)
    count = 0
    for i in range(1 << n):
        sum_subset = 0
        for j in range(n):
            if i & (1 << j):
                sum_subset += arr[j]
        if sum_subset == k:
            count += 1
    return count

# Example Usage
arr = [1, 2, 3, 4]
print(count_subsets_bitmask(arr, 5))

Output: 2

This code defines a function count_subsets_bitmask that iterates over all possible subsets (using bitwise operations) and tallies those with a sum equal to the target k. Each subset is represented as a binary number, with set bits indicating the inclusion of the corresponding element in the subset.

Bonus One-Liner Method 5: Using itertools.combinations

Python’s itertools module provides a combination function that can be used to generate all possible subsets of a given size. This one-liner approach is a Pythonic way to solve the problem using a generator expression but may not be the most efficient for large arrays.

Here’s an example:

from itertools import combinations

arr = [1, 2, 3, 4]
k = 5
count = sum(1 for i in range(len(arr) + 1) for subset in combinations(arr, i) if sum(subset) == k)
print(count)

Output: 2

This one-liner packs a lot of power, iterating over all subset sizes, generating the subsets with combinations, and summing over a generator expression that filters the subsets with the target sum k.

Summary/Discussion

  • Method 1: Recursive Approach. Understandable and straightforward. However, its performance is impractical for large sets due to its exponential time complexity.
  • Method 2: Dynamic Programming – Memoization. More efficient than plain recursion by storing and reusing results. Suitable for moderate input sizes but still uses additional memory for the memo dictionary.
  • Method 3: Dynamic Programming – Tabulation. Space-optimized and iterative, avoiding stack overflow concerns of deep recursion. It is suitable for large inputs but requires initial understanding of dynamic programming concepts.
  • Method 4: Bitmasking. Elegant and efficient for small sets. However, its time complexity grows exponentially with the size of the set, making it unsuitable for large input arrays.
  • Method 5: Using itertools.combinations. Simple and pythonic one-liner suitable for small to medium-sized arrays but may not be as memory-efficient as tabulation for larger data sets.