You are given an array of integers and a target integer. You want to find the number of ways to assign '+' or '-' signs to each integer so that the resulting expression sums to the target. Which algorithmic pattern best fits this problem?
AGreedy algorithm that picks signs to minimize absolute difference at each step
BDynamic programming using a 0/1 knapsack-like approach to count subsets with sum constraints
CDivide and conquer by splitting the array and merging counts of partial sums
DGraph traversal to find paths whose edge weights sum to the target
Step-by-Step Solution
Solution:
Step 1: Understand problem structure
The problem requires counting ways to assign signs to reach a target sum, which involves overlapping subproblems and combinatorial counting.
Step 2: Identify suitable pattern
Dynamic programming with a 0/1 knapsack pattern fits because each number can be either added or subtracted, similar to choosing subsets with sum constraints.
Final Answer:
Option B -> Option B
Quick Check:
Counting ways with sign assignments -> DP knapsack pattern [OK]
