Subsets with Constraints

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]]

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")

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 ✓

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 ✓

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

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...

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.

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}")