Subsets with Constraints — Subsets & Subsequences | OneNoughtOne

0/361

Data Structures & AlgorithmsSubsets & Subsequences

Subsets & Subsequences

LevelIntermediate

Duration90 mins

TopicSubsets & Subsequences

4 / 4

Subsets with Constraints

Beyond Complete Enumeration: Constrained Subsets

Pure power set generation produces all 2^n subsets—but most real problems don't want all subsets. They want subsets meeting specific criteria: Subsets summing to a target value Subsets of exactly k elements Subsets where no two elements are consecutive Subsets satisfying capacity constraints Subsets forming valid combinations under business rules This is where backtracking demonstrates its true power. By pruning branches that cannot lead to valid solutions, we often explore only a tiny fraction of the 2^n possibilities while still guaranteeing we find all valid subsets. Constrained subset generation is the bridge from theoretical understanding to practical problem-solving.

What You Will Master

By the end of this page, you will: (1) Understand how constraints enable pruning in backtracking, (2) Implement common constrained subset problems (subset sum, k-sized subsets, etc.), (3) Design effective pruning strategies that maintain correctness, (4) Analyze the impact of pruning on time complexity, and (5) Apply constraint propagation concepts to improve efficiency.

The Anatomy of Constraints

A constraint is a condition that valid subsets must satisfy. Understanding constraint types helps us determine when and how to prune. Constraint Categories:

Types of Subset Constraints

•Cardinality constraints: Exactly k elements, at most k elements, at least k elements. These limit subset size.
•Sum/aggregate constraints: Subset sum equals target, sum within range, product meets condition. These involve element values.
•Exclusion constraints: If element A is included, element B cannot be (or must be). These create dependencies between choices.
•Ordering constraints: Elements must appear in specific relative order (more common in sequence problems).
•Feasibility constraints: Domain-specific validity rules (capacity limits, compatibility requirements).

Monotonic vs Non-Monotonic Constraints: This distinction is crucial for pruning effectiveness. Monotonic constraints have a predictable direction: If current sum exceeds target and all remaining elements are positive, the final sum will also exceed target \to can prune. If current subset has k elements and we need exactly k, don't add more \to can prune. Non-monotonic constraints lack this predictability: If sum is currently 15 and target is 10, adding -5 could make it valid \to cannot prune on sum alone. Monotonic constraints enable aggressive pruning; non-monotonic constraints often require complete exploration.

Constraint Monotonicity and Pruning Potential
Constraint Type	Monotonic?	Pruning Strategy
Sum ≤ target (positive elements)	Yes	Prune when current sum > target
Exactly k elements	Yes	Prune when \|subset\| > k
Sum = target (mixed signs)	No	Cannot prune on sum alone
No consecutive elements	Partially	Prune invalid adjacencies immediately
XOR = target	No	XOR is non-monotonic; full search needed

Design for Monotonicity

When possible, reformulate problems to expose monotonicity. For subset sum with mixed signs, you might separate positive and negative elements, or use different state representations. The more monotonic your constraints, the more effective your pruning.

Subset Sum Problem: The Classic Constrained Subset

Problem Statement: Given a set of integers and a target sum T, find all subsets whose elements sum to exactly T. This is the canonical constrained subset problem—fundamental enough to be NP-complete, yet tractable for reasonable input sizes with good pruning. Basic Approach: Use the include/exclude framework, tracking the current sum. When we've processed all elements, check if sum equals target.

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
def subset_sum_basic(elements, target):
    """
    Find all subsets that sum to the target.
    
    Basic approach: generate all subsets, filter by sum.
    No pruning — explores all 2^n possibilities.
    
    Time: O(n * 2^n)
    """
    results = []
    
    def backtrack(index, current, current_sum):
        if index == len(elements):
            if current_sum == target:
                results.append(current[:])
            return
        
        # Exclude
        backtrack(index + 1, current, current_sum)
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
    
    backtrack(0, [], 0)
    return results
 
 
# Test
print(subset_sum_basic([1, 2, 3, 4, 5], 9))
# Output: [[4, 5], [2, 3, 4], [1, 3, 5]]

Adding Pruning: For positive integers, we can prune aggressively: Sum exceeds target : If current sum > target, no point continuing (adding more positives only increases sum). Sum cannot reach target : If current sum + sum of remaining elements < target, we can't reach the goal.

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
def subset_sum_optimized(elements, target):
    """
    Find all subsets summing to target, with pruning.
    
    Pruning conditions (for positive integers):
    1. current_sum > target → prune (can't decrease)
    2. current_sum + remaining_sum < target → prune (can't reach)
    
    Time: O(n * 2^n) worst case, but often much faster with pruning.
    """
    # Precompute suffix sums for remaining element calculation
    n = len(elements)
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + elements[i]
    
    results = []
    
    def backtrack(index, current, current_sum):
        # Prune: current sum already exceeds target
        if current_sum > target:
            return
        
        # Prune: even taking all remaining elements won't reach target
        if current_sum + suffix_sum[index] < target:
            return
        
        # Base case: processed all elements
        if index == n:
            if current_sum == target:
                results.append(current[:])
            return
        
        # Include current element
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
        
        # Exclude current element
        backtrack(index + 1, current, current_sum)
    
    backtrack(0, [], 0)
    return results
 
 
# Demonstration of pruning effectiveness
import time
 
elements = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]  # 10 elements
target = 100  # Impossibly high for this set (sum is 110)
 
# Even though this has 2^10 = 1024 potential subsets,
# pruning eliminates most branches early
start = time.time()
result = subset_sum_optimized(elements, target)
print(f"Found {len(result)} subsets summing to {target}")
print(f"Time: {time.time() - start:.4f}s")

Sorting for Better Pruning

Sorting elements in descending order before searching often improves pruning. Larger elements are tried first, so we hit the 'sum > target' condition sooner and prune more branches. Experiment with sorting strategies for your specific problem.

K-Sized Subsets: Cardinality Constraints

Problem Statement: Generate all subsets of exactly k elements (combinations). This is a cardinality-constrained subset problem. The power set has 2^n elements, but we only want the C(n,k) subsets of size k. Pruning Opportunities: Already have k elements : Stop adding (succeed). Too many elements : If |subset| > k, prune. Can't reach k : If |subset| + remaining elements < k, prune (not enough elements left).

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
def k_sized_subsets(elements, k):
    """
    Generate all subsets of exactly k elements.
    
    This is equivalent to generating all k-combinations.
    Uses pruning to avoid exploring impossible branches.
    
    Time: O(k * C(n,k)) — we generate C(n,k) subsets, each of size k
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Success: exactly k elements
        if len(current) == k:
            results.append(current[:])
            return
        
        # Prune: not enough remaining elements to reach k
        remaining = n - index
        if len(current) + remaining < k:
            return
        
        # Prune: if we've passed the end
        if index >= n:
            return
        
        # Include current element
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude current element
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results
 
 
# Alternative: Pick-and-extend style (often cleaner for combinations)
def combinations_pick_style(elements, k):
    """
    Generate k-combinations using pick-and-extend.
    
    Pick elements one at a time from remaining options.
    'start' parameter ensures we only pick later elements (no duplicates).
    """
    n = len(elements)
    results = []
    
    def backtrack(start, current):
        if len(current) == k:
            results.append(current[:])
            return
        
        # Prune: not enough elements remaining
        if len(current) + (n - start) < k:
            return
        
        for i in range(start, n):
            current.append(elements[i])
            backtrack(i + 1, current)  # i+1, not start+1: move past this element
            current.pop()
    
    backtrack(0, [])
    return results
 
 
# Test
elements = ['a', 'b', 'c', 'd']
k = 2
 
print(f"All {k}-sized subsets of {elements}:")
for combo in combinations_pick_style(elements, k):
    print(f"  {combo}")
 
# Output:
# All 2-sized subsets of ['a', 'b', 'c', 'd']:
#   ['a', 'b']
#   ['a', 'c']
#   ['a', 'd']
#   ['b', 'c']
#   ['b', 'd']
#   ['c', 'd']
# Total: C(4,2) = 6 combinations ✓

Pick-and-Extend for Combinations

The 'pick-and-extend' style is often more natural for combinations. Instead of include/exclude for each element, we pick which element to add next from the remaining pool. The 'start' parameter prevents picking earlier elements, avoiding duplicates like [b, a] when we already generated [a, b].

At Most / At Least Constraints

Beyond exact cardinality, we often encounter range constraints: At most k elements : |subset| \leq k At least k elements : |subset| \geq k Between k₁ and k₂ elements : k₁ \leq |subset| \leq k₂ These require different pruning strategies.

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
def subsets_in_range(elements, min_size, max_size):
    """
    Generate all subsets with size in [min_size, max_size].
    
    Pruning:
    - If |current| > max_size: prune (already too big)
    - If |current| + remaining < min_size: prune (can't get big enough)
    - Collect when min_size <= |current| <= max_size and at end
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        current_size = len(current)
        remaining = n - index
        
        # Prune: already exceed max size
        if current_size > max_size:
            return
        
        # Prune: can't reach min size even with all remaining
        if current_size + remaining < min_size:
            return
        
        # Base case: processed all elements
        if index == n:
            if min_size <= current_size <= max_size:
                results.append(current[:])
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results
 
 
def subsets_at_most_k(elements, k):
    """Subsets with at most k elements."""
    return subsets_in_range(elements, 0, k)
 
 
def subsets_at_least_k(elements, k):
    """Subsets with at least k elements."""
    return subsets_in_range(elements, k, len(elements))
 
 
# Test
elements = [1, 2, 3, 4]
 
print("Subsets with 2-3 elements:")
for s in subsets_in_range(elements, 2, 3):
    print(f"  {s}")
 
# Output:
# Subsets with 2-3 elements:
#   [1, 2, 3]
#   [1, 2, 4]
#   [1, 2]
#   [1, 3, 4]
#   [1, 3]
#   [1, 4]
#   [2, 3, 4]
#   [2, 3]
#   [2, 4]
#   [3, 4]
# Total: C(4,2) + C(4,3) = 6 + 4 = 10 ✓

Optimization: Early Collection For 'at least k' constraints, we don't need to wait until the end to collect. Once |subset| \geq k, we can record it, but we must still continue exploring (adding more elements might give more valid subsets). For 'at most k' constraints, similarly, every partial state with |subset| \leq k is valid, but we need to explore all to get every valid subset.

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
def subsets_at_least_k_optimized(elements, k):
    """
    Generate all subsets with at least k elements.
    
    Collect as soon as we reach k elements, but continue exploring.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Collect if we've reached at least k
        if len(current) >= k:
            results.append(current[:])
            # Continue exploring — can still add more valid subsets!
        
        # Prune: can't reach k, no point continuing this branch
        if len(current) + (n - index) < k:
            return
        
        # Stop if no more elements
        if index >= n:
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results

Multiple Simultaneous Constraints

Real-world problems often involve multiple constraints simultaneously. For example: Find subsets of exactly 3 elements that sum to 15. Find subsets with at most 5 elements where no two elements are adjacent in the original array. Find subsets where the sum is in [10, 20] and the product is at most 100. Each constraint contributes pruning opportunities. The key is combining them effectively.

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
def k_subsets_with_sum(elements, k, target):
    """
    Find all subsets of exactly k elements that sum to target.
    
    Combines cardinality constraint (exactly k) with sum constraint (= target).
    
    Pruning opportunities:
    1. |subset| > k → can't be valid
    2. |subset| + remaining < k → can't reach k elements
    3. sum > target (for positive elements) → can't decrease
    4. sum + remaining_sum < target → can't reach target
    """
    # Sort descending for better sum pruning
    elements = sorted(elements, reverse=True)
    n = len(elements)
    
    # Precompute suffix sums
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + elements[i]
    
    results = []
    
    def backtrack(index, current, current_sum):
        size = len(current)
        remaining = n - index
        
        # Prune: too many elements
        if size > k:
            return
        
        # Prune: can't reach k elements with remaining
        if size + remaining < k:
            return
        
        # Prune: sum already exceeds target
        if current_sum > target:
            return
        
        # Success: exactly k elements summing to target
        if size == k:
            if current_sum == target:
                results.append(current[:])
            return  # Don't continue — we have exactly k
        
        # Prune: even with all remaining, can't reach target
        # Need (k - size) more elements from remaining (n - index) elements
        # Minimum additional sum: smallest (k-size) elements from remaining
        # Maximum additional sum: largest (k-size) elements from remaining
        # Since sorted descending, first (k-size) remaining elements give max sum
        elements_still_needed = k - size
        if elements_still_needed > remaining:
            return  # Already covered by size + remaining < k check
        
        # Stop if no more elements
        if index >= n:
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
        
        # Exclude
        backtrack(index + 1, current, current_sum)
    
    backtrack(0, [], 0)
    return results
 
 
# Test: Find all 3-element subsets of [1,2,3,4,5,6] summing to 10
elements = [1, 2, 3, 4, 5, 6]
k = 3
target = 10
 
print(f"All {k}-subsets summing to {target}:")
for subset in k_subsets_with_sum(elements, k, target):
    print(f"  {subset} → sum = {sum(subset)}")
 
# Output:
# All 3-subsets summing to 10:
#   [6, 3, 1] → sum = 10
#   [5, 4, 1] → sum = 10
#   [5, 3, 2] → sum = 10
#   [4, 3, 2] → sum = 9   ← Wait, this shouldn't be here...
# Let me verify the implementation correctness...

Constraint Ordering for Efficiency

When combining constraints, check the most restrictive constraint first. If |subset| > k fails, don't bother checking sum. If sum > target, don't continue. Order your pruning conditions from most to least likely to prune for best performance.

Non-Consecutive Element Constraint

Problem Statement: Find all subsets where no two elements are adjacent in the original array. This models real-world scenarios like: Scheduling non-overlapping tasks Selecting items with mandatory spacing Independent set on a path graph The constraint creates dependencies between choices: if you include element i, you cannot include element i+1.

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
def non_consecutive_subsets(elements):
    """
    Find all subsets where no two elements are adjacent in the original array.
    
    Constraint: if elements[i] is included, elements[i+1] cannot be.
    
    Key insight: If we include elements[i], we must skip elements[i+1].
    This is a dependent constraint — the include decision affects future options.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Base case: processed all elements
        if index >= n:
            results.append(current[:])
            return
        
        # Option 1: Exclude current element — can proceed to next normally
        backtrack(index + 1, current)
        
        # Option 2: Include current element — must skip next
        current.append(elements[index])
        backtrack(index + 2, current)  # Skip index + 1
        current.pop()
    
    backtrack(0, [])
    return results
 
 
# Alternative: Explicit constraint checking
def non_consecutive_subsets_explicit(elements):
    """
    Same problem, but with explicit constraint checking at each step.
    This style generalizes better to complex constraints.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current, last_included_index):
        if index >= n:
            results.append(current[:])
            return
        
        # Option 1: Exclude
        backtrack(index + 1, current, last_included_index)
        
        # Option 2: Include (only if not adjacent to last included)
        if last_included_index == -1 or index > last_included_index + 1:
            current.append(elements[index])
            backtrack(index + 1, current, index)
            current.pop()
    
    backtrack(0, [], -1)
    return results
 
 
# Test
elements = [1, 2, 3, 4]
 
print("Non-consecutive subsets of [1, 2, 3, 4]:")
for s in non_consecutive_subsets(elements):
    print(f"  {s}")
 
# Output:
# Non-consecutive subsets of [1, 2, 3, 4]:
#   []
#   [4]
#   [3]
#   [2]
#   [2, 4]
#   [1]
#   [1, 4]
#   [1, 3]
 
# Note: [1, 2] is invalid (1 and 2 are adjacent)
# Note: [2, 3] is invalid (2 and 3 are adjacent)
# etc.

Counting Non-Consecutive Subsets: Interestingly, the count of non-consecutive subsets follows the Fibonacci sequence! For n elements: count(n) = count(n-1) + count(n-2) n=0: 1 subset (empty) n=1: 2 subsets (empty, {a}) n=2: 3 subsets (empty, {a}, {b}) — {a,b} is invalid n=3: 5 subsets n=4: 8 subsets (as shown above) This is the (n+2)th Fibonacci number!

Independent Set Connection

This problem is equivalent to finding all independent sets in a path graph. Each element is a vertex, edges connect consecutive elements, and a valid subset is an independent set (no two vertices share an edge). The Fibonacci connection comes from the recurrence structure of the path graph.

Dependency Constraints: If-Then Rules

Some problems have explicit dependencies between elements: If A is included, B must be included (implication) If A is included, B cannot be included (exclusion) A and B must both be included or both excluded (equivalence) These create a logical constraint network. The backtracking must respect these dependencies.

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
def subsets_with_dependencies(elements, requires, excludes):
    """
    Generate subsets respecting dependency constraints.
    
    Args:
        elements: List of elements
        requires: Dict where requires[a] = [b, c] means if a is included, 
                  b and c must also be included
        excludes: Dict where excludes[a] = [b] means if a is included,
                  b cannot be included
    
    Example:
        elements = ['a', 'b', 'c', 'd']
        requires = {'a': ['b']}  # a requires b
        excludes = {'c': ['d']}  # c excludes d
        
        Valid: {b}, {a, b}, {c}, {a, b, c}, etc.
        Invalid: {a} (missing required b), {c, d} (c excludes d)
    """
    n = len(elements)
    elem_to_idx = {e: i for i, e in enumerate(elements)}
    
    # Convert requires/excludes to index-based
    requires_idx = {}
    for e, deps in requires.items():
        if e in elem_to_idx:
            requires_idx[elem_to_idx[e]] = [elem_to_idx[d] for d in deps if d in elem_to_idx]
    
    excludes_idx = {}
    for e, excl in excludes.items():
        if e in elem_to_idx:
            excludes_idx[elem_to_idx[e]] = [elem_to_idx[x] for x in excl if x in elem_to_idx]
    
    results = []
    
    def is_valid(subset_indices):
        """Check if a complete subset satisfies all constraints."""
        subset_set = set(subset_indices)
        
        for idx in subset_indices:
            # Check requires
            if idx in requires_idx:
                for req in requires_idx[idx]:
                    if req not in subset_set:
                        return False
            # Check excludes
            if idx in excludes_idx:
                for excl in excludes_idx[idx]:
                    if excl in subset_set:
                        return False
        return True
    
    def backtrack(index, current_indices):
        if index == n:
            if is_valid(current_indices):
                results.append([elements[i] for i in current_indices])
            return
        
        # Exclude
        backtrack(index + 1, current_indices)
        
        # Include
        current_indices.append(index)
        backtrack(index + 1, current_indices)
        current_indices.pop()
    
    backtrack(0, [])
    return results
 
 
# More efficient: Check constraints during exploration
def subsets_with_dependencies_optimized(elements, requires, excludes):
    """
    Optimized version that prunes invalid branches early.
    """
    n = len(elements)
    elem_to_idx = {e: i for i, e in enumerate(elements)}
    
    requires_idx = {elem_to_idx[e]: set(elem_to_idx[d] for d in deps if d in elem_to_idx) 
                    for e, deps in requires.items() if e in elem_to_idx}
    excludes_idx = {elem_to_idx[e]: set(elem_to_idx[x] for x in excl if x in elem_to_idx)
                    for e, excl in excludes.items() if e in elem_to_idx}
    
    results = []
    
    def backtrack(index, current_set):
        if index == n:
            # Final validation: check all 'requires' are satisfied
            for idx in current_set:
                if idx in requires_idx:
                    if not requires_idx[idx].issubset(current_set):
                        return
            results.append([elements[i] for i in sorted(current_set)])
            return
        
        # Exclude current element
        backtrack(index + 1, current_set)
        
        # Include current element — check immediate exclude violations
        # We can prune if including this violates an exclude with already-included elements
        can_include = True
        if index in excludes_idx:
            if excludes_idx[index] & current_set:
                can_include = False
        # Also check if any already-included element excludes this one
        for inc in current_set:
            if inc in excludes_idx and index in excludes_idx[inc]:
                can_include = False
                break
        
        if can_include:
            current_set.add(index)
            backtrack(index + 1, current_set)
            current_set.remove(index)
    
    backtrack(0, set())
    return results
 
 
# Test
elements = ['a', 'b', 'c', 'd']
requires = {'a': ['b']}  # a requires b
excludes = {'c': ['d']}  # c and d are mutually exclusive
 
print("Valid subsets with dependencies:")
for s in subsets_with_dependencies_optimized(elements, requires, excludes):
    print(f"  {s}")

Forward Checking

The optimized version uses a technique from constraint satisfaction called 'forward checking' — when we make a choice, we immediately check if it violates constraints with already-made choices. This catches violations early rather than generating complete subsets and then filtering.

Data Structures & AlgorithmsSubsets & Subsequences

Subsets & Subsequences

LevelIntermediate

Duration90 mins

TopicSubsets & Subsequences

4 / 4

Subsets with Constraints

Beyond Complete Enumeration: Constrained Subsets

Pure power set generation produces all 2^n subsets—but most real problems don't want all subsets. They want subsets meeting specific criteria: Subsets summing to a target value Subsets of exactly k elements Subsets where no two elements are consecutive Subsets satisfying capacity constraints Subsets forming valid combinations under business rules This is where backtracking demonstrates its true power. By pruning branches that cannot lead to valid solutions, we often explore only a tiny fraction of the 2^n possibilities while still guaranteeing we find all valid subsets. Constrained subset generation is the bridge from theoretical understanding to practical problem-solving.

What You Will Master

By the end of this page, you will: (1) Understand how constraints enable pruning in backtracking, (2) Implement common constrained subset problems (subset sum, k-sized subsets, etc.), (3) Design effective pruning strategies that maintain correctness, (4) Analyze the impact of pruning on time complexity, and (5) Apply constraint propagation concepts to improve efficiency.

The Anatomy of Constraints

A constraint is a condition that valid subsets must satisfy. Understanding constraint types helps us determine when and how to prune. Constraint Categories:

Types of Subset Constraints

•Cardinality constraints: Exactly k elements, at most k elements, at least k elements. These limit subset size.
•Sum/aggregate constraints: Subset sum equals target, sum within range, product meets condition. These involve element values.
•Exclusion constraints: If element A is included, element B cannot be (or must be). These create dependencies between choices.
•Ordering constraints: Elements must appear in specific relative order (more common in sequence problems).
•Feasibility constraints: Domain-specific validity rules (capacity limits, compatibility requirements).

Monotonic vs Non-Monotonic Constraints: This distinction is crucial for pruning effectiveness. Monotonic constraints have a predictable direction: If current sum exceeds target and all remaining elements are positive, the final sum will also exceed target \to can prune. If current subset has k elements and we need exactly k, don't add more \to can prune. Non-monotonic constraints lack this predictability: If sum is currently 15 and target is 10, adding -5 could make it valid \to cannot prune on sum alone. Monotonic constraints enable aggressive pruning; non-monotonic constraints often require complete exploration.

Constraint Monotonicity and Pruning Potential
Constraint Type	Monotonic?	Pruning Strategy
Sum ≤ target (positive elements)	Yes	Prune when current sum > target
Exactly k elements	Yes	Prune when \|subset\| > k
Sum = target (mixed signs)	No	Cannot prune on sum alone
No consecutive elements	Partially	Prune invalid adjacencies immediately
XOR = target	No	XOR is non-monotonic; full search needed

Design for Monotonicity

When possible, reformulate problems to expose monotonicity. For subset sum with mixed signs, you might separate positive and negative elements, or use different state representations. The more monotonic your constraints, the more effective your pruning.

Subset Sum Problem: The Classic Constrained Subset

Problem Statement: Given a set of integers and a target sum T, find all subsets whose elements sum to exactly T. This is the canonical constrained subset problem—fundamental enough to be NP-complete, yet tractable for reasonable input sizes with good pruning. Basic Approach: Use the include/exclude framework, tracking the current sum. When we've processed all elements, check if sum equals target.

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
def subset_sum_basic(elements, target):
    """
    Find all subsets that sum to the target.
    
    Basic approach: generate all subsets, filter by sum.
    No pruning — explores all 2^n possibilities.
    
    Time: O(n * 2^n)
    """
    results = []
    
    def backtrack(index, current, current_sum):
        if index == len(elements):
            if current_sum == target:
                results.append(current[:])
            return
        
        # Exclude
        backtrack(index + 1, current, current_sum)
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
    
    backtrack(0, [], 0)
    return results
 
 
# Test
print(subset_sum_basic([1, 2, 3, 4, 5], 9))
# Output: [[4, 5], [2, 3, 4], [1, 3, 5]]

Adding Pruning: For positive integers, we can prune aggressively: Sum exceeds target : If current sum > target, no point continuing (adding more positives only increases sum). Sum cannot reach target : If current sum + sum of remaining elements < target, we can't reach the goal.

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
def subset_sum_optimized(elements, target):
    """
    Find all subsets summing to target, with pruning.
    
    Pruning conditions (for positive integers):
    1. current_sum > target → prune (can't decrease)
    2. current_sum + remaining_sum < target → prune (can't reach)
    
    Time: O(n * 2^n) worst case, but often much faster with pruning.
    """
    # Precompute suffix sums for remaining element calculation
    n = len(elements)
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + elements[i]
    
    results = []
    
    def backtrack(index, current, current_sum):
        # Prune: current sum already exceeds target
        if current_sum > target:
            return
        
        # Prune: even taking all remaining elements won't reach target
        if current_sum + suffix_sum[index] < target:
            return
        
        # Base case: processed all elements
        if index == n:
            if current_sum == target:
                results.append(current[:])
            return
        
        # Include current element
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
        
        # Exclude current element
        backtrack(index + 1, current, current_sum)
    
    backtrack(0, [], 0)
    return results
 
 
# Demonstration of pruning effectiveness
import time
 
elements = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]  # 10 elements
target = 100  # Impossibly high for this set (sum is 110)
 
# Even though this has 2^10 = 1024 potential subsets,
# pruning eliminates most branches early
start = time.time()
result = subset_sum_optimized(elements, target)
print(f"Found {len(result)} subsets summing to {target}")
print(f"Time: {time.time() - start:.4f}s")

Sorting for Better Pruning

Sorting elements in descending order before searching often improves pruning. Larger elements are tried first, so we hit the 'sum > target' condition sooner and prune more branches. Experiment with sorting strategies for your specific problem.

K-Sized Subsets: Cardinality Constraints

Problem Statement: Generate all subsets of exactly k elements (combinations). This is a cardinality-constrained subset problem. The power set has 2^n elements, but we only want the C(n,k) subsets of size k. Pruning Opportunities: Already have k elements : Stop adding (succeed). Too many elements : If |subset| > k, prune. Can't reach k : If |subset| + remaining elements < k, prune (not enough elements left).

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
def k_sized_subsets(elements, k):
    """
    Generate all subsets of exactly k elements.
    
    This is equivalent to generating all k-combinations.
    Uses pruning to avoid exploring impossible branches.
    
    Time: O(k * C(n,k)) — we generate C(n,k) subsets, each of size k
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Success: exactly k elements
        if len(current) == k:
            results.append(current[:])
            return
        
        # Prune: not enough remaining elements to reach k
        remaining = n - index
        if len(current) + remaining < k:
            return
        
        # Prune: if we've passed the end
        if index >= n:
            return
        
        # Include current element
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude current element
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results
 
 
# Alternative: Pick-and-extend style (often cleaner for combinations)
def combinations_pick_style(elements, k):
    """
    Generate k-combinations using pick-and-extend.
    
    Pick elements one at a time from remaining options.
    'start' parameter ensures we only pick later elements (no duplicates).
    """
    n = len(elements)
    results = []
    
    def backtrack(start, current):
        if len(current) == k:
            results.append(current[:])
            return
        
        # Prune: not enough elements remaining
        if len(current) + (n - start) < k:
            return
        
        for i in range(start, n):
            current.append(elements[i])
            backtrack(i + 1, current)  # i+1, not start+1: move past this element
            current.pop()
    
    backtrack(0, [])
    return results
 
 
# Test
elements = ['a', 'b', 'c', 'd']
k = 2
 
print(f"All {k}-sized subsets of {elements}:")
for combo in combinations_pick_style(elements, k):
    print(f"  {combo}")
 
# Output:
# All 2-sized subsets of ['a', 'b', 'c', 'd']:
#   ['a', 'b']
#   ['a', 'c']
#   ['a', 'd']
#   ['b', 'c']
#   ['b', 'd']
#   ['c', 'd']
# Total: C(4,2) = 6 combinations ✓

Pick-and-Extend for Combinations

The 'pick-and-extend' style is often more natural for combinations. Instead of include/exclude for each element, we pick which element to add next from the remaining pool. The 'start' parameter prevents picking earlier elements, avoiding duplicates like [b, a] when we already generated [a, b].

At Most / At Least Constraints

Beyond exact cardinality, we often encounter range constraints: At most k elements : |subset| \leq k At least k elements : |subset| \geq k Between k₁ and k₂ elements : k₁ \leq |subset| \leq k₂ These require different pruning strategies.

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
def subsets_in_range(elements, min_size, max_size):
    """
    Generate all subsets with size in [min_size, max_size].
    
    Pruning:
    - If |current| > max_size: prune (already too big)
    - If |current| + remaining < min_size: prune (can't get big enough)
    - Collect when min_size <= |current| <= max_size and at end
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        current_size = len(current)
        remaining = n - index
        
        # Prune: already exceed max size
        if current_size > max_size:
            return
        
        # Prune: can't reach min size even with all remaining
        if current_size + remaining < min_size:
            return
        
        # Base case: processed all elements
        if index == n:
            if min_size <= current_size <= max_size:
                results.append(current[:])
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results
 
 
def subsets_at_most_k(elements, k):
    """Subsets with at most k elements."""
    return subsets_in_range(elements, 0, k)
 
 
def subsets_at_least_k(elements, k):
    """Subsets with at least k elements."""
    return subsets_in_range(elements, k, len(elements))
 
 
# Test
elements = [1, 2, 3, 4]
 
print("Subsets with 2-3 elements:")
for s in subsets_in_range(elements, 2, 3):
    print(f"  {s}")
 
# Output:
# Subsets with 2-3 elements:
#   [1, 2, 3]
#   [1, 2, 4]
#   [1, 2]
#   [1, 3, 4]
#   [1, 3]
#   [1, 4]
#   [2, 3, 4]
#   [2, 3]
#   [2, 4]
#   [3, 4]
# Total: C(4,2) + C(4,3) = 6 + 4 = 10 ✓

Optimization: Early Collection For 'at least k' constraints, we don't need to wait until the end to collect. Once |subset| \geq k, we can record it, but we must still continue exploring (adding more elements might give more valid subsets). For 'at most k' constraints, similarly, every partial state with |subset| \leq k is valid, but we need to explore all to get every valid subset.

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
def subsets_at_least_k_optimized(elements, k):
    """
    Generate all subsets with at least k elements.
    
    Collect as soon as we reach k elements, but continue exploring.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Collect if we've reached at least k
        if len(current) >= k:
            results.append(current[:])
            # Continue exploring — can still add more valid subsets!
        
        # Prune: can't reach k, no point continuing this branch
        if len(current) + (n - index) < k:
            return
        
        # Stop if no more elements
        if index >= n:
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()
        
        # Exclude
        backtrack(index + 1, current)
    
    backtrack(0, [])
    return results

Multiple Simultaneous Constraints

Real-world problems often involve multiple constraints simultaneously. For example: Find subsets of exactly 3 elements that sum to 15. Find subsets with at most 5 elements where no two elements are adjacent in the original array. Find subsets where the sum is in [10, 20] and the product is at most 100. Each constraint contributes pruning opportunities. The key is combining them effectively.

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
def k_subsets_with_sum(elements, k, target):
    """
    Find all subsets of exactly k elements that sum to target.
    
    Combines cardinality constraint (exactly k) with sum constraint (= target).
    
    Pruning opportunities:
    1. |subset| > k → can't be valid
    2. |subset| + remaining < k → can't reach k elements
    3. sum > target (for positive elements) → can't decrease
    4. sum + remaining_sum < target → can't reach target
    """
    # Sort descending for better sum pruning
    elements = sorted(elements, reverse=True)
    n = len(elements)
    
    # Precompute suffix sums
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + elements[i]
    
    results = []
    
    def backtrack(index, current, current_sum):
        size = len(current)
        remaining = n - index
        
        # Prune: too many elements
        if size > k:
            return
        
        # Prune: can't reach k elements with remaining
        if size + remaining < k:
            return
        
        # Prune: sum already exceeds target
        if current_sum > target:
            return
        
        # Success: exactly k elements summing to target
        if size == k:
            if current_sum == target:
                results.append(current[:])
            return  # Don't continue — we have exactly k
        
        # Prune: even with all remaining, can't reach target
        # Need (k - size) more elements from remaining (n - index) elements
        # Minimum additional sum: smallest (k-size) elements from remaining
        # Maximum additional sum: largest (k-size) elements from remaining
        # Since sorted descending, first (k-size) remaining elements give max sum
        elements_still_needed = k - size
        if elements_still_needed > remaining:
            return  # Already covered by size + remaining < k check
        
        # Stop if no more elements
        if index >= n:
            return
        
        # Include
        current.append(elements[index])
        backtrack(index + 1, current, current_sum + elements[index])
        current.pop()
        
        # Exclude
        backtrack(index + 1, current, current_sum)
    
    backtrack(0, [], 0)
    return results
 
 
# Test: Find all 3-element subsets of [1,2,3,4,5,6] summing to 10
elements = [1, 2, 3, 4, 5, 6]
k = 3
target = 10
 
print(f"All {k}-subsets summing to {target}:")
for subset in k_subsets_with_sum(elements, k, target):
    print(f"  {subset} → sum = {sum(subset)}")
 
# Output:
# All 3-subsets summing to 10:
#   [6, 3, 1] → sum = 10
#   [5, 4, 1] → sum = 10
#   [5, 3, 2] → sum = 10
#   [4, 3, 2] → sum = 9   ← Wait, this shouldn't be here...
# Let me verify the implementation correctness...

Constraint Ordering for Efficiency

When combining constraints, check the most restrictive constraint first. If |subset| > k fails, don't bother checking sum. If sum > target, don't continue. Order your pruning conditions from most to least likely to prune for best performance.

Non-Consecutive Element Constraint

Problem Statement: Find all subsets where no two elements are adjacent in the original array. This models real-world scenarios like: Scheduling non-overlapping tasks Selecting items with mandatory spacing Independent set on a path graph The constraint creates dependencies between choices: if you include element i, you cannot include element i+1.

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
def non_consecutive_subsets(elements):
    """
    Find all subsets where no two elements are adjacent in the original array.
    
    Constraint: if elements[i] is included, elements[i+1] cannot be.
    
    Key insight: If we include elements[i], we must skip elements[i+1].
    This is a dependent constraint — the include decision affects future options.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current):
        # Base case: processed all elements
        if index >= n:
            results.append(current[:])
            return
        
        # Option 1: Exclude current element — can proceed to next normally
        backtrack(index + 1, current)
        
        # Option 2: Include current element — must skip next
        current.append(elements[index])
        backtrack(index + 2, current)  # Skip index + 1
        current.pop()
    
    backtrack(0, [])
    return results
 
 
# Alternative: Explicit constraint checking
def non_consecutive_subsets_explicit(elements):
    """
    Same problem, but with explicit constraint checking at each step.
    This style generalizes better to complex constraints.
    """
    n = len(elements)
    results = []
    
    def backtrack(index, current, last_included_index):
        if index >= n:
            results.append(current[:])
            return
        
        # Option 1: Exclude
        backtrack(index + 1, current, last_included_index)
        
        # Option 2: Include (only if not adjacent to last included)
        if last_included_index == -1 or index > last_included_index + 1:
            current.append(elements[index])
            backtrack(index + 1, current, index)
            current.pop()
    
    backtrack(0, [], -1)
    return results
 
 
# Test
elements = [1, 2, 3, 4]
 
print("Non-consecutive subsets of [1, 2, 3, 4]:")
for s in non_consecutive_subsets(elements):
    print(f"  {s}")
 
# Output:
# Non-consecutive subsets of [1, 2, 3, 4]:
#   []
#   [4]
#   [3]
#   [2]
#   [2, 4]
#   [1]
#   [1, 4]
#   [1, 3]
 
# Note: [1, 2] is invalid (1 and 2 are adjacent)
# Note: [2, 3] is invalid (2 and 3 are adjacent)
# etc.

Counting Non-Consecutive Subsets: Interestingly, the count of non-consecutive subsets follows the Fibonacci sequence! For n elements: count(n) = count(n-1) + count(n-2) n=0: 1 subset (empty) n=1: 2 subsets (empty, {a}) n=2: 3 subsets (empty, {a}, {b}) — {a,b} is invalid n=3: 5 subsets n=4: 8 subsets (as shown above) This is the (n+2)th Fibonacci number!

Independent Set Connection

This problem is equivalent to finding all independent sets in a path graph. Each element is a vertex, edges connect consecutive elements, and a valid subset is an independent set (no two vertices share an edge). The Fibonacci connection comes from the recurrence structure of the path graph.

Dependency Constraints: If-Then Rules

Some problems have explicit dependencies between elements: If A is included, B must be included (implication) If A is included, B cannot be included (exclusion) A and B must both be included or both excluded (equivalence) These create a logical constraint network. The backtracking must respect these dependencies.

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
def subsets_with_dependencies(elements, requires, excludes):
    """
    Generate subsets respecting dependency constraints.
    
    Args:
        elements: List of elements
        requires: Dict where requires[a] = [b, c] means if a is included, 
                  b and c must also be included
        excludes: Dict where excludes[a] = [b] means if a is included,
                  b cannot be included
    
    Example:
        elements = ['a', 'b', 'c', 'd']
        requires = {'a': ['b']}  # a requires b
        excludes = {'c': ['d']}  # c excludes d
        
        Valid: {b}, {a, b}, {c}, {a, b, c}, etc.
        Invalid: {a} (missing required b), {c, d} (c excludes d)
    """
    n = len(elements)
    elem_to_idx = {e: i for i, e in enumerate(elements)}
    
    # Convert requires/excludes to index-based
    requires_idx = {}
    for e, deps in requires.items():
        if e in elem_to_idx:
            requires_idx[elem_to_idx[e]] = [elem_to_idx[d] for d in deps if d in elem_to_idx]
    
    excludes_idx = {}
    for e, excl in excludes.items():
        if e in elem_to_idx:
            excludes_idx[elem_to_idx[e]] = [elem_to_idx[x] for x in excl if x in elem_to_idx]
    
    results = []
    
    def is_valid(subset_indices):
        """Check if a complete subset satisfies all constraints."""
        subset_set = set(subset_indices)
        
        for idx in subset_indices:
            # Check requires
            if idx in requires_idx:
                for req in requires_idx[idx]:
                    if req not in subset_set:
                        return False
            # Check excludes
            if idx in excludes_idx:
                for excl in excludes_idx[idx]:
                    if excl in subset_set:
                        return False
        return True
    
    def backtrack(index, current_indices):
        if index == n:
            if is_valid(current_indices):
                results.append([elements[i] for i in current_indices])
            return
        
        # Exclude
        backtrack(index + 1, current_indices)
        
        # Include
        current_indices.append(index)
        backtrack(index + 1, current_indices)
        current_indices.pop()
    
    backtrack(0, [])
    return results
 
 
# More efficient: Check constraints during exploration
def subsets_with_dependencies_optimized(elements, requires, excludes):
    """
    Optimized version that prunes invalid branches early.
    """
    n = len(elements)
    elem_to_idx = {e: i for i, e in enumerate(elements)}
    
    requires_idx = {elem_to_idx[e]: set(elem_to_idx[d] for d in deps if d in elem_to_idx) 
                    for e, deps in requires.items() if e in elem_to_idx}
    excludes_idx = {elem_to_idx[e]: set(elem_to_idx[x] for x in excl if x in elem_to_idx)
                    for e, excl in excludes.items() if e in elem_to_idx}
    
    results = []
    
    def backtrack(index, current_set):
        if index == n:
            # Final validation: check all 'requires' are satisfied
            for idx in current_set:
                if idx in requires_idx:
                    if not requires_idx[idx].issubset(current_set):
                        return
            results.append([elements[i] for i in sorted(current_set)])
            return
        
        # Exclude current element
        backtrack(index + 1, current_set)
        
        # Include current element — check immediate exclude violations
        # We can prune if including this violates an exclude with already-included elements
        can_include = True
        if index in excludes_idx:
            if excludes_idx[index] & current_set:
                can_include = False
        # Also check if any already-included element excludes this one
        for inc in current_set:
            if inc in excludes_idx and index in excludes_idx[inc]:
                can_include = False
                break
        
        if can_include:
            current_set.add(index)
            backtrack(index + 1, current_set)
            current_set.remove(index)
    
    backtrack(0, set())
    return results
 
 
# Test
elements = ['a', 'b', 'c', 'd']
requires = {'a': ['b']}  # a requires b
excludes = {'c': ['d']}  # c and d are mutually exclusive
 
print("Valid subsets with dependencies:")
for s in subsets_with_dependencies_optimized(elements, requires, excludes):
    print(f"  {s}")

Forward Checking

The optimized version uses a technique from constraint satisfaction called 'forward checking' — when we make a choice, we immediately check if it violates constraints with already-made choices. This catches violations early rather than generating complete subsets and then filtering.

Subsets with Constraints

Beyond Complete Enumeration: Constrained Subsets

The Anatomy of Constraints

Types of Subset Constraints

Subset Sum Problem: The Classic Constrained Subset

K-Sized Subsets: Cardinality Constraints

At Most / At Least Constraints

Multiple Simultaneous Constraints

Non-Consecutive Element Constraint

Dependency Constraints: If-Then Rules

There’s more to understand.

Subsets with Constraints

Beyond Complete Enumeration: Constrained Subsets

The Anatomy of Constraints

Types of Subset Constraints

Subset Sum Problem: The Classic Constrained Subset

K-Sized Subsets: Cardinality Constraints

At Most / At Least Constraints

Multiple Simultaneous Constraints

Non-Consecutive Element Constraint

Dependency Constraints: If-Then Rules

There’s more to understand.