Knapsack Problems - Learning Module

Loading content...

0/276

Subset Sum — A Specialized Knapsack Problem

The Foundational Decision Problem

Can you select items from a set such that their values sum to exactly a target? This deceptively simple question defines the Subset Sum problem—one of the most fundamental problems in computer science.

Subset Sum sits at the intersection of many domains:

It's one of Karp's original 21 NP-complete problems (1972)
It forms the basis of some cryptographic systems
It appears in countless practical scenarios: budget allocation, partition problems, scheduling
It's a stepping stone toward understanding more complex optimization problems

What makes Subset Sum particularly elegant is its direct relationship to the 0/1 Knapsack problem. In fact, Subset Sum is precisely 0/1 Knapsack where each item's value equals its weight! This correspondence enables us to apply our knapsack expertise directly, while the problem's special structure yields additional insights and optimizations.

What You Will Learn

By the end of this page, you will understand Subset Sum as a specialized knapsack problem, implement efficient solutions, explore important variations (counting subsets, partition problems, bounded targets), and recognize how Subset Sum appears in interview and competition problems.

The Subset Sum Problem

The Decision Version:

Given a set of n positive integers S = {a₁, a₂, ..., aₙ} and a target sum T, determine whether there exists a subset of S whose elements sum to exactly T.

Mathematical Formulation:

$$\text{Does there exist } X \subseteq S \text{ such that } \sum_{a \in X} a = T \text{ ?}$$

Mapping to 0/1 Knapsack:

Subset Sum	0/1 Knapsack
Numbers aᵢ	Items with weight = value = aᵢ
Target T	Capacity W
Sum exactly T?	Can we fill exactly capacity W?

The key insight: in 0/1 Knapsack, if we set v[i] = w[i] for all items, then maximizing value is equivalent to maximizing weight used. If the maximum weight we can use is exactly T, then Subset Sum is solvable.

Example Subset Sum Instance
Set Elements	Target	Subset Exists?	Solution
{3, 7, 1, 8, 4}	15	Yes	{3, 8, 4}
{3, 7, 1, 8, 4}	2	No	—
{3, 7, 1, 8, 4}	23	Yes	{3, 7, 1, 8, 4} (all)
{2, 4, 6, 8}	11	No	— (all even, target odd)

The Boolean DP Formulation

Unlike general 0/1 Knapsack which tracks maximum value, Subset Sum only needs to track reachability—can we achieve this sum or not? This leads to a cleaner boolean formulation.

State Definition: dp[i][s] = true if we can achieve sum s using elements from {a₁, a₂, ..., aᵢ}, false otherwise.

Recurrence:

dp[i][s] = dp[i-1][s]           // Exclude aᵢ: can we reach s without aᵢ?
         OR dp[i-1][s - aᵢ]     // Include aᵢ: can we reach s - aᵢ without aᵢ?

Base Cases:

dp[0][0] = true — With no elements, sum 0 is achievable (empty subset)
dp[0][s] = false for s > 0 — With no elements, positive sums are impossible

Boolean vs Value DP

In 0/1 Knapsack, we compute maximum values (integers). In Subset Sum, we compute reachability (booleans). This simplification:

Reduces to OR operations instead of MAX
Often allows bit manipulation optimizations
Makes the logic more transparent

Final Answer:

The answer to "Can we achieve target T?" is simply dp[n][T].

Complexity:

Time: O(n × T) — for each of n elements and T possible sums
Space: O(n × T) for 2D table, or O(T) with space optimization

Implementation: Decision and Reconstruction

Let's implement Subset Sum with both the decision answer and subset reconstruction.

subset_sum.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
def subset_sum_exists(nums: list[int], target: int) -> bool:
    """
    Determine if any subset sums to exactly target.
    
    Time: O(n * target), Space: O(target)
    """
    if target < 0:
        return False
    if target == 0:
        return True  # Empty subset
    
    # dp[s] = True if sum s is achievable
    dp = [False] * (target + 1)
    dp[0] = True  # Empty subset achieves sum 0
    
    for num in nums:
        # Process right to left to avoid using same element twice
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True
    
    return dp[target]
 
 
def subset_sum_find(nums: list[int], target: int) -> list[int] | None:
    """
    Find a subset that sums to exactly target, or None if impossible.
    
    Returns list of indices of elements in the subset.
    """
    n = len(nums)
    
    # dp[i][s] = True if sum s is achievable using elements 0..i-1
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # Exclude current element
            dp[i][s] = dp[i - 1][s]
            # Include current element (if possible)
            if s >= num and dp[i - 1][s - num]:
                dp[i][s] = True
    
    if not dp[n][target]:
        return None
    
    # Backtrack to find the subset
    result = []
    s = target
    for i in range(n, 0, -1):
        # If dp[i][s] but not dp[i-1][s], then element i-1 was included
        if not dp[i - 1][s]:
            result.append(i - 1)
            s -= nums[i - 1]
    
    result.reverse()
    return result
 
 
def subset_sum_2d_visualization(nums: list[int], target: int):
    """
    Solve with full 2D table for visualization.
    """
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= num:
                dp[i][s] = dp[i][s] or dp[i - 1][s - num]
    
    # Print table
    print("Subset Sum DP Table:")
    print("    ", end="")
    for s in range(target + 1):
        print(f"{s:3}", end=" ")
    print()
    
    for i in range(n + 1):
        label = f"a{nums[i-1]}" if i > 0 else "∅"
        print(f"{label:3} ", end="")
        for s in range(target + 1):
            print(" T " if dp[i][s] else " . ", end=" ")
        print()
    
    return dp[n][target]
 
 
# Example usage
if __name__ == "__main__":
    nums = [3, 7, 1, 8, 4]
    target = 15
    
    exists = subset_sum_exists(nums, target)
    subset = subset_sum_find(nums, target)
    
    print(f"Numbers: {nums}")
    print(f"Target: {target}")
    print(f"Subset exists: {exists}")
    if subset:
        print(f"Subset indices: {subset}")
        print(f"Subset elements: {[nums[i] for i in subset]}")
        print(f"Sum: {sum(nums[i] for i in subset)}")
    
    print("\n--- Table Visualization ---")
    subset_sum_2d_visualization(nums, target)

Critical: Right-to-Left Fill Order for 1D

When using a 1D DP array for 0/1-style subset sum, we must iterate sums from target down to num (right to left). This prevents using the same element multiple times within one iteration.

Incorrect (left to right): dp[4] might use num=2 twice: dp[2] + 2 = dp[4] Correct (right to left): By the time we update dp[4], dp[2] still reflects the previous iteration.

Counting Subsets with Target Sum

A natural extension: instead of asking "Does a subset exist?", ask "How many subsets sum to T?"

Modified Recurrence:

dp[i][s] = dp[i-1][s] + dp[i-1][s - aᵢ]

Instead of OR (does either path work?), we ADD (count both paths).

Base Case:

dp[0][0] = 1 — One way to achieve sum 0: the empty subset
dp[0][s] = 0 for s > 0 — No way to achieve positive sum with no elements

count_subsets.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def count_subsets_with_sum(nums: list[int], target: int) -> int:
    """
    Count the number of subsets that sum to exactly target.
    
    Note: If nums contains zeros, each zero doubles the count
    (since {subset} and {subset + zero} both achieve the same sum).
    
    Time: O(n * target), Space: O(target)
    """
    if target < 0:
        return 0
    
    # dp[s] = number of subsets achieving sum s
    dp = [0] * (target + 1)
    dp[0] = 1  # One way to achieve sum 0: empty subset
    
    for num in nums:
        # Right to left to avoid counting same element twice
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[target]
 
 
def count_subsets_2d(nums: list[int], target: int) -> int:
    """
    2D version for clarity and debugging.
    """
    n = len(nums)
    dp = [[0] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]  # Exclude
            if s >= num:
                dp[i][s] += dp[i - 1][s - num]  # Include
    
    return dp[n][target]
 
 
# Example
if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    target = 5
    
    count = count_subsets_with_sum(nums, target)
    print(f"Numbers: {nums}")
    print(f"Target sum: {target}")
    print(f"Number of subsets: {count}")
    
    # Let's enumerate them
    print("\nEnumerating subsets:")
    from itertools import combinations
    all_subsets = []
    for r in range(len(nums) + 1):
        for combo in combinations(nums, r):
            if sum(combo) == target:
                all_subsets.append(combo)
                print(f"  {combo}")
    print(f"Total: {len(all_subsets)}")

Handling Zeros:

Zeros require special attention. A zero can be included or excluded without changing the sum, so each zero effectively multiplies the count by 2.

Strategy: Filter zeros first, count subsets for nonzero elements, then multiply by 2^(number of zeros).

Alternatively, initialize dp[0] = 1 and let the algorithm naturally count—but be aware that zeros will bloat the count if not handled intentionally.

The Partition Problem

One of the most elegant applications of Subset Sum is the Partition Problem:

Problem: Given a set of integers, can we partition them into two subsets such that both subsets have equal sum?

Reduction to Subset Sum:

If the total sum is S, we need two subsets each summing to S/2.

If S is odd, partition is impossible (can't split odd sum equally)
If S is even, find if any subset sums to S/2
If such a subset exists, the remaining elements automatically sum to S/2

This elegant reduction makes partition no harder than subset sum!

partition.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
def can_partition(nums: list[int]) -> bool:
    """
    Determine if nums can be partitioned into two equal-sum subsets.
    
    Also known as: Equal Subset Sum Partition
    LeetCode 416: Partition Equal Subset Sum
    """
    total = sum(nums)
    
    # Odd total can't be split equally
    if total % 2 == 1:
        return False
    
    target = total // 2
    
    # Subset sum for target
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]
    
    return dp[target]
 
 
def partition_into_subsets(nums: list[int]) -> tuple[list[int], list[int]] | None:
    """
    Find the actual partition if it exists.
    Returns (subset1, subset2) or None.
    """
    total = sum(nums)
    if total % 2 == 1:
        return None
    
    target = total // 2
    n = len(nums)
    
    # 2D DP for backtracking
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= num:
                dp[i][s] = dp[i][s] or dp[i - 1][s - num]
    
    if not dp[n][target]:
        return None
    
    # Backtrack for subset1
    subset1_indices = set()
    s = target
    for i in range(n, 0, -1):
        if not dp[i - 1][s]:
            subset1_indices.add(i - 1)
            s -= nums[i - 1]
    
    subset1 = [nums[i] for i in range(n) if i in subset1_indices]
    subset2 = [nums[i] for i in range(n) if i not in subset1_indices]
    
    return subset1, subset2
 
 
def min_subset_sum_difference(nums: list[int]) -> int:
    """
    Partition nums into two subsets minimizing the difference.
    
    Strategy: Find the largest achievable sum <= total/2.
    One subset gets that sum, the other gets the rest.
    """
    total = sum(nums)
    target = total // 2
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]
    
    # Find largest achievable sum <= target
    for s in range(target, -1, -1):
        if dp[s]:
            subset1_sum = s
            subset2_sum = total - s
            return abs(subset2_sum - subset1_sum)
    
    return total  # Fallback (should never reach if all positive)
 
 
# Example
if __name__ == "__main__":
    nums = [1, 5, 11, 5]
    
    print(f"Numbers: {nums}")
    print(f"Total: {sum(nums)}")
    
    result = partition_into_subsets(nums)
    if result:
        s1, s2 = result
        print(f"Partition possible!")
        print(f"  Subset 1: {s1}, sum = {sum(s1)}")
        print(f"  Subset 2: {s2}, sum = {sum(s2)}")
    else:
        print("Exact partition not possible")
        min_diff = min_subset_sum_difference(nums)
        print(f"Minimum difference partition: {min_diff}")

Minimum Difference Partition

When exact equal partition is impossible, we often want to minimize the difference between subset sums. Strategy: find the largest achievable subset sum ≤ total/2. This gives us the closest possible approximation to an equal split.

Bitset Optimization

Since Subset Sum uses boolean values, we can leverage bitwise operations for significant speedup. The key insight: a boolean array dp can be represented as a single large integer (bitset), where bit position s indicates whether sum s is achievable.

Bitset Transition:

For element num, the update:

dp[s] = dp[s] OR dp[s - num]  for all s >= num

becomes a single bitwise operation:

dp = dp | (dp << num)

The left shift << num shifts all achievable sums up by num, and the OR combines with existing sums.

subset_sum_bitset.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
def subset_sum_bitset(nums: list[int], target: int) -> bool:
    """
    Subset Sum using Python's arbitrary-precision integers as bitsets.
    
    Bit i of 'dp' is 1 iff sum i is achievable.
    
    Time: O(n * target / word_size), practically O(n * target / 64)
    Space: O(target / word_size)
    
    Often 32-64x faster than boolean array approach!
    """
    # dp = 1 means bit 0 is set: sum 0 is achievable (empty subset)
    dp = 1
    
    for num in nums:
        # Shift left by num and OR with original
        # This adds 'num' to all previously achievable sums
        dp |= dp << num
    
    # Check if bit 'target' is set
    return (dp >> target) & 1 == 1
 
 
def count_achievable_sums(nums: list[int], max_sum: int) -> list[int]:
    """
    Find all achievable sums from 0 to max_sum using bitset.
    """
    dp = 1
    
    for num in nums:
        dp |= dp << num
    
    # Mask to only consider sums up to max_sum
    dp &= (1 << (max_sum + 1)) - 1
    
    # Extract all set bits
    achievable = []
    s = 0
    while dp:
        if dp & 1:
            achievable.append(s)
        dp >>= 1
        s += 1
    
    return achievable
 
 
def subset_sum_with_negatives(nums: list[int], target: int) -> bool:
    """
    Subset Sum when numbers can be negative.
    
    Strategy: Offset all sums to make them non-negative.
    """
    # Calculate offset: the most negative possible sum
    negative_sum = sum(x for x in nums if x < 0)
    offset = -negative_sum
    
    # Adjusted target and maximum sum
    adjusted_target = target + offset
    max_sum = sum(abs(x) for x in nums) + offset
    
    if adjusted_target < 0 or adjusted_target > max_sum:
        return False
    
    # Bitset approach with offset
    dp = 1 << offset  # Sum 0 is at bit position 'offset'
    
    for num in nums:
        if num >= 0:
            dp |= dp << num
        else:
            dp |= dp >> (-num)
    
    return (dp >> adjusted_target) & 1 == 1
 
 
# Performance comparison
if __name__ == "__main__":
    import time
    import random
    
    # Generate test case
    random.seed(42)
    nums = [random.randint(1, 100) for _ in range(500)]
    target = sum(nums) // 3
    
    # Boolean array approach
    start = time.time()
    dp_bool = [False] * (target + 1)
    dp_bool[0] = True
    for num in nums:
        for s in range(target, num - 1, -1):
            if dp_bool[s - num]:
                dp_bool[s] = True
    result_bool = dp_bool[target]
    time_bool = time.time() - start
    
    # Bitset approach
    start = time.time()
    result_bitset = subset_sum_bitset(nums, target)
    time_bitset = time.time() - start
    
    print(f"Boolean array: {result_bool}, time: {time_bool*1000:.2f}ms")
    print(f"Bitset: {result_bitset}, time: {time_bitset*1000:.2f}ms")
    print(f"Speedup: {time_bool/time_bitset:.1f}x")

Why Bitset Is Faster

Modern CPUs process 64 bits in a single operation. The boolean array processes one boolean per operation. Bitset gives roughly 64x speedup for the inner loop, often bringing Subset Sum from TLE (Time Limit Exceeded) to AC (Accepted) in competitive programming!

Common Subset Sum Variations

Subset Sum appears in many forms across interview and competition problems. Recognizing these variations helps you apply the pattern quickly.

Subset Sum Variations
Variation	Description	Key Modification
Target Sum with +/-	Assign + or - to each element to reach target	Transform: target' = (target + sum) / 2
K-Sum	Find k elements summing to target	3D DP: dp[i][count][sum]
Subset Sum with repetition	Each element can be used multiple times	Use Unbounded Knapsack pattern
Bounded Subset Sum	Each element has max count	Multiply elements or use bounded knapsack
Subset Sum modulo m	Find subset with sum ≡ 0 (mod m)	Track sums mod m instead of actual sums

target_sum_plus_minus.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def find_target_sum_ways(nums: list[int], target: int) -> int:
    """
    LeetCode 494: Target Sum
    
    Assign + or - to each number to achieve target sum.
    Count the number of ways.
    
    Key insight: If P is sum of numbers with +, and N is sum with -:
    - P + N = total_sum
    - P - N = target
    Therefore: P = (total_sum + target) / 2
    
    This reduces to: count subsets with sum = P
    """
    total = sum(nums)
    
    # Check feasibility
    if (total + target) % 2 != 0:
        return 0  # No integer solution for P
    if abs(target) > total:
        return 0  # Target unreachable
    
    p_sum = (total + target) // 2
    
    if p_sum < 0:
        return 0
    
    # Count subsets summing to p_sum
    dp = [0] * (p_sum + 1)
    dp[0] = 1
    
    for num in nums:
        for s in range(p_sum, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[p_sum]
 
 
# Example: LeetCode 494
if __name__ == "__main__":
    nums = [1, 1, 1, 1, 1]
    target = 3
    
    ways = find_target_sum_ways(nums, target)
    print(f"Numbers: {nums}")
    print(f"Target: {target}")
    print(f"Number of ways: {ways}")
    
    # Enumerate for verification
    from itertools import product
    count = 0
    for signs in product([1, -1], repeat=len(nums)):
        if sum(s * n for s, n in zip(signs, nums)) == target:
            count += 1
    print(f"Verified by enumeration: {count}")

The +/- Transformation

The Target Sum problem transformation is a beautiful example of problem reduction. By expressing the constraints algebraically (P + N = total, P - N = target), we derive P = (total + target) / 2, converting a seemingly different problem into straightforward subset sum counting.

NP-Completeness and Practical Implications

Subset Sum is NP-Complete, meaning (under standard assumptions) no polynomial-time algorithm exists. Yet our O(n × T) dynamic programming solution often works well in practice. How do we reconcile this?

Pseudo-Polynomial vs Polynomial:

Our algorithm runs in O(n × T) where T is the target value. This is:

Polynomial in the numeric value of T
Exponential in the number of bits needed to represent T

If T = 2^k, we do O(n × 2^k) work—exponential in k (the input size for T). This is pseudo-polynomial, not truly polynomial.

When DP Works:

T is moderate (≤ 10^6 or so)
n is reasonable (≤ 10^3-10^4)
Numbers are small relative to n

When DP Fails:

T is huge (10^18)
Numbers are very large
Cryptographic contexts (designed to resist this)

Complexity Scenarios
Scenario	n	T (max sum)	States	Feasible?
Interview typical	20-30	~1000	~30,000	✓ Trivial
LeetCode medium	100-200	~10^4	~2×10^6	✓ Easy
Competition	1000	~10^6	~10^9	⚠️ Bitset needed
Cryptographic	~50	~10^15	~10^17	✗ Infeasible

Alternative Approaches for Large Instances:

Meet-in-the-Middle: Split items into two halves, enumerate all 2^(n/2) sums for each half, then use two-pointer or binary search to find matching pairs. Complexity: O(2^(n/2) × n) — feasible for n ≤ 40.
Approximation: For optimization variants, FPTAS (Fully Polynomial-Time Approximation Scheme) can find (1+ε)-approximate solutions in polynomial time.
Randomized Methods: Probability-based approaches can sometimes detect solvability quickly, though without guarantees.

NP-Hardness Intuition

The subset sum decision is like finding a needle in a haystack of 2^n subsets. DP succeeds when the haystack collapses—when many subsets share the same sum, we don't need to track them separately. When sums are all distinct (large, random numbers), DP offers no compression and we're back to exponential.

Summary: Subset Sum Mastery

We've completed a comprehensive exploration of Subset Sum—from its formulation as a specialized knapsack problem to advanced optimizations and practical applications.

Key Takeaways

•Subset Sum is 0/1 Knapsack with v[i] = w[i]: This equivalence lets us apply all knapsack techniques directly.
•Boolean DP suffices: We track reachability (can we achieve sum s?) rather than maximum values, simplifying the logic to OR operations.
•Counting extends naturally: Replace OR with ADD to count subsets achieving each sum.
•Partition reduces to Subset Sum: Find if any subset sums to total/2 to determine equal partition feasibility.
•Bitset optimization dramatically speeds up: Leverage CPU word parallelism for 32-64x speedups.
•The +/- Target Sum transforms elegantly: Mathematical manipulation converts the problem to standard subset sum counting.
•Pseudo-polynomial complexity: O(n × T) works when T is moderate, but fails for exponentially large targets.

Module Complete:

With this page, you've mastered the entire Knapsack family of problems:

0/1 Knapsack: Binary item selection with capacity constraint
State Design: Why capacity remaining is the key dimension
Unbounded Knapsack: Unlimited item selection and its 1D simplification
Subset Sum: Boolean reachability as specialized knapsack

These patterns form the backbone of resource-constrained optimization in dynamic programming.

Module Complete

Congratulations! You now have deep mastery of Knapsack Problems—the classic paradigm for constrained optimization in dynamic programming. You can recognize knapsack patterns, choose appropriate variants (0/1, unbounded, subset sum), implement efficient solutions, and optimize with advanced techniques like bitset manipulation.