💡 Problem Formulation: The task is to find the total number of subsequences of an array whose sum equals a specific target value. Given an input array [3,1,2,1] and a target sum 3, an algorithm should output the number of subsequences that sum up to the target, which here is 3: [3], [1,2], and [2,1].
Method 1: Recursive Approach
Using recursion, we can explore all possible subsequences by choosing or excluding each element. The recursive function has two parameters: the current index and the current sum. If we reach the target sum, we increment our count. This method is easy to understand but has exponential time complexity.
Here’s an example:
def count_subsequences(arr, n, target_sum):
if target_sum == 0:
return 1
if n == 0:
return 0
count = count_subsequences(arr, n-1, target_sum)
if arr[n-1] <= target_sum:
count += count_subsequences(arr, n-1, target_sum-arr[n-1])
return count
arr = [3, 1, 2, 1]
target_sum = 3
print(count_subsequences(arr, len(arr), target_sum))
Output: 3
This code defines a function count_subsequences which recursively computes the count of subsequences with the given sum. If the current element can be included, the function calls itself twice – once including the element and once excluding it. The base cases handle situations where the target sum is achieved or the array is exhausted.
Method 2: Dynamic Programming
Dynamic programming improves the recursive approach by remembering solutions to subproblems. We create a memoization table to store results of subproblems to avoid recomputation. This method has a complexity of O(n*sum), where n is the size of the array and sum is the target sum.
Here’s an example:
def count_subsequences(arr, target_sum):
n = len(arr)
dp = [[0 for _ in range(target_sum + 1)] for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, target_sum + 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][target_sum]
arr = [3, 1, 2, 1]
target_sum = 3
print(count_subsequences(arr, target_sum))
Output: 3
The count_subsequences function builds up a table dp where dp[i][j] represents the count of subsequences using the first i elements of arr that sum up to j. The function iterates over each element, updating the table based on previously computed values.
Method 3: Backtracking
Backtracking is an optimization over the recursive approach that halts the recursion early if the current sum exceeds the target. It’s more efficient than plain recursion as it doesn’t explore paths that obviously don’t lead to a solution, but still has a high time complexity in the worst case.
Here’s an example:
def count_subsequences(arr, start, n, target_sum):
if target_sum == 0:
return 1
count = 0
for i in range(start, n):
if target_sum - arr[i] >= 0:
count += count_subsequences(arr, i + 1, n, target_sum - arr[i])
return count
arr = [3, 1, 2, 1]
target_sum = 3
print(count_subsequences(arr, 0, len(arr), target_sum))
Output: 3
This count_subsequences function utilizes backtracking by iterating over the array and recursively calling itself for each subsequence. It reduces the target sum by the current element’s value and continues only if the remaining sum is non-negative.
Method 4: Bitmasking
Bitmasking leverages binary numbers to represent inclusion or exclusion of elements. Each subsequence can be represented by a binary number where the i-th bit indicates the presence of the i-th element. By iterating over all 2^n possible combinations, we can calculate their sums and count those that equal the target sum.
Here’s an example:
def count_subsequences(arr, target_sum):
n = len(arr)
count = 0
for i in range(1, 1 << n):
sum = 0
for j in range(n):
if i & (1 << j):
sum += arr[j]
if sum == target_sum:
count += 1
return count
arr = [3, 1, 2, 1]
target_sum = 3
print(count_subsequences(arr, target_sum))
Output: 3
The function count_subsequences iterates through all possible subsets created using bitmasks. For each subset, it calculates the sum and checks if it matches the target. The bitwise operations & and << are used for efficiently testing inclusion in the subset.
Bonus One-Liner Method 5: Using Combinations with Filter
This Python one-liner uses itertools.combinations to generate all possible subsequences and then filters those whose sum equals the target sum. The length of this filtered list is the count of required subsequences. This method is elegant but not suitable for large arrays due to combinatorial explosion.
Here’s an example:
from itertools import combinations arr = [3, 1, 2, 1] target_sum = 3 print(len([combo for r in range(len(arr)+1) for combo in combinations(arr, r) if sum(combo) == target_sum]))
Output: 3
The provided one-liner iterates through all combination lengths r and selects those subsequences from arr which, when summed up, match the target_sum. Although concise, this method can be very slow for large arrays.
Summary/Discussion
- Method 1: Recursive Approach. Simple, intuitive but very slow for large input due to its O(2^n) complexity.
- Method 2: Dynamic Programming. More efficient, O(n*sum) complexity; however, can consume considerable memory for large inputs.
- Method 3: Backtracking. Prunes unnecessary paths for improved performance over recursion but still inefficient for large datasets.
- Method 4: Bitmasking. Good for small datasets as it’s straightforward and fast but scales poorly due to O(2^n) complexity.
- Bonus Method 5: One-Liner with Combinations. Extremely concise, a good fit for small datasets and one-offs, but impractical for large lists.