State Design & Transition Functions

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

# ===== BASE CASE: Empty Subproblem =====
def coin_change(coins: list[int], amount: int) -> int:
    """
    State: dp[a] = minimum coins to make amount a
    
    BASE CASE: dp[0] = 0
    Meaning: Zero coins needed to make amount 0.
    
    Why not -inf or inf?
        - Amount 0 IS achievable (by taking nothing)
        - The answer (0 coins) is the correct minimum
        - If dp[0] = inf, transitions would propagate incorrect values
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins for amount 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != float('inf'):
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
 
# ===== BASE CASE: Multiple Base Values =====
def climbing_stairs(n: int) -> int:
    """
    State: dp[i] = ways to reach step i
    
    BASE CASES:
        dp[0] = 1  # One way to "reach" the ground (do nothing)
        dp[1] = 1  # One way to reach step 1 (single step)
    
    Why dp[0] = 1?
        - This might seem odd (there's no "step 0")
        - But semantically: "ways to have climbed 0 steps" = 1 (the empty path)
        - This makes transitions work: dp[2] = dp[1] + dp[0] = 1 + 1 = 2 ✓
    """
    if n <= 1:
        return 1
    
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1  # Both base cases
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
 
 
# ===== BASE CASE: Grid Boundaries =====
def unique_paths(m: int, n: int) -> int:
    """
    State: dp[r][c] = paths to reach cell (r, c)
    
    BASE CASES:
        dp[0][c] = 1 for all c  # First row: only one path (all right)
        dp[r][0] = 1 for all r  # First column: only one path (all down)
    
    These are semantic: there's exactly one way to reach any cell
    in the first row (keep going right) or first column (keep going down).
    """
    dp = [[0] * n for _ in range(m)]
    
    # Base cases: boundaries
    for c in range(n):
        dp[0][c] = 1
    for r in range(m):
        dp[r][0] = 1
    
    # Transition: interior cells
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    
    return dp[m-1][n-1]
 
 
# ===== BASE CASE: Two Sequences =====
def edit_distance(word1: str, word2: str) -> int:
    """
    State: dp[i][j] = min edits for word1[0..i-1] → word2[0..j-1]
    
    BASE CASES:
        dp[0][j] = j  # Inserting j characters into empty string
        dp[i][0] = i  # Deleting i characters to get empty string
        dp[0][0] = 0  # Empty → empty requires 0 edits
    
    The base cases form an "L shape" along the first row and column.
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base case: first column (word2 is empty)
    for i in range(m + 1):
        dp[i][0] = i  # i deletions
    
    # Base case: first row (word1 is empty)
    for j in range(n + 1):
        dp[0][j] = j  # j insertions
    
    # Note: dp[0][0] = 0 is set by both loops (correctly)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]
 
 
# ===== BASE CASE: Interval DP =====
def longest_palindrome_subseq(s: str) -> int:
    """
    State: dp[i][j] = length of longest palindromic subsequence in s[i..j]
    
    BASE CASES:
        dp[i][i] = 1     # Single character is a palindrome of length 1
        dp[i][i-1] = 0   # "Empty" interval (when i > j) has length 0
                         # This handles the j-1 < i case in transitions
    
    For interval DP, base cases are typically the smallest intervals
    (length 0 and 1), from which we build larger ones.
    """
    n = len(s)
    if n == 0:
        return 0
    
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = 1
    
    # Build larger intervals
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                # dp[i+1][j-1] might be "empty" if length == 2
                # That's okay: dp[i+1][i] = 0 (implicitly handled)
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    return dp[0][n-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
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

# ===== EMPTY INPUT: Return Trivial Answer =====
def longest_increasing_subsequence(nums: list[int]) -> int:
    """
    EMPTY CASE: nums = []
    
    Expected: 0 (no subsequence of any length exists)
    
    Handle early to avoid issues with dp array indexing and max().
    """
    if not nums:
        return 0  # Explicit early return
    
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)  # Safe now since nums is non-empty
 
 
# ===== EMPTY INPUT: Different Semantics =====
def word_break(s: str, wordDict: list[str]) -> bool:
    """
    EMPTY CASES:
        s = ""      → True (empty string is trivially segmented)
        wordDict=[] → False (unless s is empty)
    
    These semantics come from the problem definition:
        Can the string be segmented using dictionary words?
        Empty string = yes, even with empty dictionary.
    """
    if not s:
        return True  # Empty string is always segmentable
    
    word_set = set(wordDict)
    if not word_set:
        return False  # Non-empty string, no words = impossible
    
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Base case: empty prefix is segmentable
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]
 
 
# ===== MINIMAL INPUT: Single Element =====
def house_robber(nums: list[int]) -> int:
    """
    MINIMAL CASES:
        nums = []  → 0 (nothing to rob)
        nums = [x] → x (rob the only house)
        nums = [x, y] → max(x, y) (can only rob one)
    
    These must be handled explicitly because the main loop
    starts at i=2 and would access dp[1], dp[0].
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums[0], nums[1])
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]
 
 
# ===== MINIMAL INPUT: 1×1 Grid =====
def min_path_sum(grid: list[list[int]]) -> int:
    """
    MINIMAL CASES:
        1×1 grid: return grid[0][0]
        1×n or n×1: only one path exists
    
    Main logic handles these if boundaries are correct.
    """
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # First row (handles 1×n case)
    for c in range(1, n):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    
    # First column (handles n×1 case)
    for r in range(1, m):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    
    # Interior (empty if m=1 or n=1)
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + grid[r][c]
    
    return dp[m-1][n-1]  # Works for 1×1 too: dp[0][0] = grid[0][0]

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

# ===== STRATEGY 1: Padding =====
def lcs_with_padding(text1: str, text2: str) -> int:
    """
    Use (m+1) × (n+1) table so indices never go negative.
    
    dp[i][j] represents LCS of text1[0..i-1] and text2[0..j-1]
    dp[0][j] and dp[i][0] are empty string cases (value 0)
    """
    m, n = len(text1), len(text2)
    
    # Padded table: m+1 rows, n+1 columns
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # Row 0 and column 0 are implicitly 0 (base cases)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # Safe: i-1 >= 0, j-1 >= 0
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Safe indices
    
    return dp[m][n]
 
 
# ===== STRATEGY 2: Explicit Bounds Checking =====
def max_subarray_dp(nums: list[int]) -> int:
    """
    dp[i] = maximum subarray sum ending at index i
    
    Transition: dp[i] = max(nums[i], dp[i-1] + nums[i])
    
    Need to handle i=0 specially.
    """
    if not nums:
        return 0  # Or raise exception, depending on problem
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]  # Base case: first element
    
    for i in range(1, n):  # Start from 1 to avoid i-1 = -1
        dp[i] = max(nums[i], dp[i-1] + nums[i])
    
    return max(dp)
 
 
# Alternative with check inside loop:
def max_subarray_dp_v2(nums: list[int]) -> int:
    """Version with explicit check instead of starting loop at 1."""
    if not nums:
        return 0
    
    n = len(nums)
    dp = [0] * n
    
    for i in range(n):
        if i == 0:
            dp[i] = nums[i]
        else:
            dp[i] = max(nums[i], dp[i-1] + nums[i])
    
    return max(dp)
 
 
# ===== STRATEGY 3: Sentinel Values =====
def minimum_falling_path_sum(matrix: list[list[int]]) -> int:
    """
    Can move to positions (r+1, c-1), (r+1, c), (r+1, c+1).
    
    Problem: accessing c-1 or c+1 at boundaries is out of bounds.
    Solution: Pad with inf sentinels on left and right.
    """
    if not matrix or not matrix[0]:
        return 0
    
    n = len(matrix)
    INF = float('inf')
    
    # Pad each row with inf on both sides
    # Original: matrix[r] = [a, b, c, ...]
    # Padded:   row = [inf, a, b, c, ..., inf]
    
    prev = [INF] + matrix[0][:] + [INF]  # Previous row, padded
    
    for r in range(1, n):
        curr = [INF] + [0] * n + [INF]  # Current row, padded
        for c in range(1, n + 1):  # 1-indexed due to padding
            curr[c] = matrix[r][c-1] + min(
                prev[c-1],  # Diagonal left (c-1 is safe)
                prev[c],    # Directly above
                prev[c+1]   # Diagonal right (c+1 is safe due to right padding)
            )
        prev = curr
    
    return min(prev[1:n+1])  # Exclude padding sentinels
 
 
# ===== COMMON BUG: Off-by-one in Loop Bounds =====
def demonstrate_loop_bound_issues():
    """
    Common mistakes with loop bounds:
    
    MISTAKE 1: Wrong direction
        for i in range(n-1, 0, -1):  # Stops at 1, misses 0!
        for i in range(n-1, -1, -1): # Correct: goes from n-1 to 0
    
    MISTAKE 2: Inclusive vs exclusive
        for i in range(n):     # i goes 0 to n-1 (correct for 0-indexed)
        for i in range(1, n+1): # i goes 1 to n (correct for 1-indexed strings)
    
    MISTAKE 3: Nested loop dependencies
        for i in range(n):
            for j in range(i):  # j goes 0 to i-1, not including i
            for j in range(i+1): # j goes 0 to i, including i
    """
    pass

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141

# ===== ZERO: Target Zero in Subset Sum =====
def subset_sum_zero_target(nums: list[int], target: int) -> bool:
    """
    EDGE CASE: target = 0
    
    Is there a subset summing to 0?
    Answer: Always yes (the empty subset).
    
    This is why dp[0] = True in subset sum problems.
    """
    if target == 0:
        return True  # Empty subset
    
    if target < 0 or not nums:
        return False
    
    dp = [False] * (target + 1)
    dp[0] = True  # Base case: sum 0 is achievable
    
    for num in nums:
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True
    
    return dp[target]
 
 
# ===== ZERO: Zero Values in Array =====
def max_product_subarray(nums: list[int]) -> int:
    """
    EDGE CASE: zeros in the array
    
    Zero "resets" the product chain. The answer might be:
    - A subarray before a zero
    - A subarray after a zero
    - Just the zero itself (if all others are negative with odd count)
    
    Track both max and min products (for negative handling).
    """
    if not nums:
        return 0
    
    max_so_far = nums[0]
    min_ending = max_ending = nums[0]
    
    for i in range(1, len(nums)):
        num = nums[i]
        
        if num == 0:
            # Zero resets everything
            min_ending = max_ending = 0
        else:
            candidates = [num, max_ending * num, min_ending * num]
            max_ending = max(candidates)
            min_ending = min(candidates)
        
        max_so_far = max(max_so_far, max_ending)
    
    return max_so_far
 
 
# ===== NEGATIVE: Negative Numbers in Target Sum =====
def target_sum_with_negatives(nums: list[int], target: int) -> int:
    """
    EDGE CASE: target can be negative
    
    Standard subset sum doesn't handle negative targets directly.
    Transform: find subsets P, N where P - N = target.
    """
    total = sum(nums)
    
    # P - N = target, P + N = total
    # 2P = target + total
    # P = (target + total) / 2
    
    if (target + total) % 2 != 0:
        return 0
    
    p_sum = (target + total) // 2
    
    # Handle negative p_sum edge case
    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]
 
 
# ===== INFINITY: Safe Initialization and Arithmetic =====
def coin_change_safe_infinity(coins: list[int], amount: int) -> int:
    """
    ISSUE: Using float('inf') can cause issues in some languages.
           Using INT_MAX and adding 1 causes overflow.
    
    SAFE APPROACH: Use amount + 1 as "infinity"
    Since minimum coins for any amount <= amount is at most 'amount'
    (using 1-value coins), amount + 1 is safely "unreachable."
    """
    INF = amount + 1  # Safe infinity: no valid answer can exceed 'amount'
    
    dp = [INF] * (amount + 1)
    dp[0] = 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)  # Safe: no overflow
    
    return dp[amount] if dp[amount] < INF else -1
 
 
# ===== NEGATIVE: Min/Max with Negatives =====
def max_sum_with_negatives(nums: list[int]) -> int:
    """
    EDGE CASE: All numbers are negative
    
    Maximum subarray sum should be the least negative (closest to 0).
    Kadane's algorithm handles this naturally.
    """
    if not nums:
        return 0
    
    max_ending = max_so_far = nums[0]
    
    for i in range(1, len(nums)):
        max_ending = max(nums[i], max_ending + nums[i])
        max_so_far = max(max_so_far, max_ending)
    
    return max_so_far
 
 
# Test: all negatives
# nums = [-3, -1, -4]
# Should return -1 (the "largest" negative, i.e., closest to 0)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

# ===== IMPOSSIBLE: No Valid Solution =====
def coin_change_impossible(coins: list[int], amount: int) -> int:
    """
    Case: amount = 11, coins = [3, 7]
    
    Cannot make 11 with 3s and 7s (11 = 3a + 7b has no non-negative solution).
    
    Detection: dp[11] remains at infinity after all transitions.
    Return: -1 to indicate impossible.
    """
    if amount == 0:
        return 0
    
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != INF:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    # Check if solution exists
    if dp[amount] == INF:
        return -1  # Impossible
    return dp[amount]
 
 
# ===== IMPOSSIBLE: Unreachable States in Grids =====
def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
    """
    Some cells are blocked (grid[r][c] = 1).
    dp[r][c] = 0 if blocked (no paths through this cell).
    
    Edge case: start or end is blocked → return 0.
    """
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    
    # Edge case: start or end blocked
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0
    
    dp = [[0] * n for _ in range(m)]
    
    # First cell
    dp[0][0] = 1
    
    # First row: blocked cell stops path propagation
    for c in range(1, n):
        dp[0][c] = 0 if grid[0][c] == 1 else dp[0][c-1]
    
    # First column
    for r in range(1, m):
        dp[r][0] = 0 if grid[r][0] == 1 else dp[r-1][0]
    
    # Interior
    for r in range(1, m):
        for c in range(1, n):
            if grid[r][c] == 1:
                dp[r][c] = 0  # Blocked: no paths
            else:
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
    
    return dp[m-1][n-1]
 
 
# ===== IMPOSSIBLE: Jump Game (Can We Reach End?) =====
def can_jump(nums: list[int]) -> bool:
    """
    nums[i] = max jump distance from position i.
    
    Impossible case: get stuck at a position with 0 before reaching end.
    
    Greedy approach: track farthest reachable position.
    """
    if not nums:
        return True  # Or False, depending on problem definition
    
    farthest = 0
    n = len(nums)
    
    for i in range(n):
        if i > farthest:
            return False  # Cannot reach position i
        farthest = max(farthest, i + nums[i])
        if farthest >= n - 1:
            return True
    
    return farthest >= n - 1
 
 
# ===== IMPOSSIBLE: Word Break (No Valid Segmentation) =====
def word_break_impossible(s: str, wordDict: list[str]) -> bool:
    """
    Case: s = "catsdog", wordDict = ["cats", "dog"]
    But what if s = "catsdogs"? No valid segmentation.
    
    All dp[i] will remain False except dp[0].
    Final answer dp[n] = False indicates impossibility.
    """
    word_set = set(wordDict)
    n = len(s)
    
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]  # False if no segmentation exists
 
 
# ===== IMPOSSIBLE: Multiple Impossibility Reasons =====
def partition_equal_subset_impossible(nums: list[int]) -> bool:
    """
    Impossible cases:
    1. Total sum is odd → cannot split into two equal halves
    2. Single element → cannot split (unless it's 0)
    3. All elements sum to target, but no subset achieves it exactly
    
    Handle each case appropriately.
    """
    if not nums:
        return True  # Empty set can be trivially partitioned
    
    total = sum(nums)
    
    # Case 1: odd sum
    if total % 2 != 0:
        return False
    
    target = total // 2
    
    # Case 2 implicitly handled (single element would need to be 0)
    
    # DP to check if subset sum = target exists
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True
    
    return dp[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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def run_edge_case_tests(solution_fn, test_cases: list[tuple]) -> None:
    """
    Template for systematic edge case testing.
    
    test_cases: list of (input, expected_output, description)
    """
    for i, (inputs, expected, description) in enumerate(test_cases):
        result = solution_fn(*inputs) if isinstance(inputs, tuple) else solution_fn(inputs)
        status = "✓" if result == expected else "✗"
        print(f"{status} Test {i+1}: {description}")
        if result != expected:
            print(f"   Expected: {expected}, Got: {result}")
 
 
# Example: Testing Coin Change
def test_coin_change():
    from typing import List
    
    def coin_change(coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for coin in coins:
                if coin <= a and dp[a - coin] != float('inf'):
                    dp[a] = min(dp[a], dp[a - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1
    
    tests = [
        # (inputs, expected, description)
        (([1, 2, 5], 0), 0, "Zero amount"),
        (([1, 2, 5], 1), 1, "Single coin exact"),
        (([2], 1), -1, "Impossible - no way to make 1"),
        (([1], 5), 5, "Single denomination"),
        (([], 5), -1, "Empty coins - impossible"),
        (([1, 2, 5], 11), 3, "Standard case - 5+5+1"),
        (([2, 5], 3), -1, "Impossible - gaps in coverage"),
        (([1, 2, 5], 100), 20, "Large amount"),
    ]
    
    run_edge_case_tests(coin_change, tests)
 
 
# Run tests
if __name__ == "__main__":
    test_coin_change()