Subset Sum DP — Left-to-Right Bug Reuses Items

import java.util.Arrays;

public class SubsetSumMemoized {

    // memo[index][remainingTarget] = 1 (reachable), 0 (not reachable), -1 (unvisited)
    private static int[][] memo;

    public static void main(String[] args) {
        int[] numbers = {3, 34, 4, 12, 5, 2};
        int target = 9;

        // Initialize memo table with -1 to signal "not yet computed"
        memo = new int[numbers.length][target + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        boolean canReachTarget = hasSubsetWithSum(numbers, numbers.length - 1, target);
        System.out.println("Input: " + Arrays.toString(numbers));
        System.out.println("Target: " + target);
        System.out.println("Subset exists: " + canReachTarget); // {4, 5} or {3, 4, 2}
    }

    /**
     * Top-down DP with memoization.
     *
     * @param numbers       the input array
     * @param currentIndex  we consider elements from index 0..currentIndex
     * @param remaining     how much target sum is still needed
     * @return true if some subset of numbers[0..currentIndex] sums to remaining
     */
    private static boolean hasSubsetWithSum(int[] numbers, int currentIndex, int remaining) {
        // Base case 1: remaining target is exactly 0 — empty subset achieves this
        if (remaining == 0) return true;

        // Base case 2: no elements left to consider and target not yet met
        if (currentIndex < 0) return false;

        // Base case 3: current element is larger than remaining target — can only skip it
        // (all elements assumed non-negative; including it would overshoot)
        if (numbers[currentIndex] > remaining) {
            if (memo[currentIndex][remaining] == -1) {
                memo[currentIndex][remaining] =
                    hasSubsetWithSum(numbers, currentIndex - 1, remaining) ? 1 : 0;
            }
            return memo[currentIndex][remaining] == 1;
        }

        // Return cached result if available
        if (memo[currentIndex][remaining] != -1) {
            return memo[currentIndex][remaining] == 1;
        }

        // Core decision: skip the current element OR include it (subtract its value)
        boolean result =
            hasSubsetWithSum(numbers, currentIndex - 1, remaining) ||
            hasSubsetWithSum(numbers, currentIndex - 1, remaining - numbers[currentIndex]);

        memo[currentIndex][remaining] = result ? 1 : 0;
        return result;
    }
}

import java.util.Arrays;

public class SubsetSumDP2D {

    public static void main(String[] args) {
        int[] numbers = {3, 34, 4, 12, 5, 2};
        int target = 9;

        boolean found = canAchieveTarget(numbers, target);
        System.out.println("Input: " + Arrays.toString(numbers));
        System.out.println("Target: " + target);
        System.out.println("Subset with sum " + target + " exists: " + found);

        // Also print which subset was found by backtracking the table
        printSubset(numbers, target);
    }

    public static boolean canAchieveTarget(int[] numbers, int targetSum) {
        int n = numbers.length;

        // dp[i][s] = true means: using first i numbers, sum s is achievable
        boolean[][] dp = new boolean[n + 1][targetSum + 1];

        // Base case: sum of 0 is always achievable (pick nothing)
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // Fill the table row by row (element by element)
        for (int i = 1; i <= n; i++) {
            int currentElement = numbers[i - 1]; // i-th element (1-indexed row, 0-indexed array)

            for (int sum = 1; sum <= targetSum; sum++) {
                // Option 1: skip the current element — inherit answer from previous row
                dp[i][sum] = dp[i - 1][sum];

                // Option 2: include the current element, if it doesn't overshoot
                if (sum >= currentElement) {
                    // If (sum - currentElement) was reachable without this element, now sum is reachable
                    dp[i][sum] = dp[i][sum] || dp[i - 1][sum - currentElement];
                }
            }
        }

        return dp[n][targetSum];
    }

    /**
     * Backtracks through the filled DP table to reconstruct one valid subset.
     * This is a critical skill — the table tells you IF a solution exists;
     * backtracking tells you WHAT the solution is.
     */
    public static void printSubset(int[] numbers, int targetSum) {
        int n = numbers.length;
        boolean[][] dp = new boolean[n + 1][targetSum + 1];

        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            int currentElement = numbers[i - 1];
            for (int sum = 1; sum <= targetSum; sum++) {
                dp[i][sum] = dp[i - 1][sum];
                if (sum >= currentElement) {
                    dp[i][sum] = dp[i][sum] || dp[i - 1][sum - currentElement];
                }
            }
        }

        if (!dp[n][targetSum]) {
            System.out.println("No valid subset found.");
            return;
        }

        // Backtrack: start from dp[n][target] and walk back to dp[0][0]
        int remainingSum = targetSum;
        System.out.print("One valid subset: {");
        boolean first = true;
        for (int i = n; i > 0 && remainingSum > 0; i--) {
            // If dp[i][remainingSum] != dp[i-1][remainingSum], element i was INCLUDED
            if (!dp[i - 1][remainingSum]) {
                if (!first) System.out.print(", ");
                System.out.print(numbers[i - 1]);
                remainingSum -= numbers[i - 1]; // subtract included element and move left
                first = false;
            }
            // Otherwise, element i was skipped — move up the row without changing remainingSum
        }
        System.out.println("}");
    }
}

import java.util.Arrays;

public class SubsetSumOptimized {

    public static void main(String[] args) {
        int[] numbers = {3, 34, 4, 12, 5, 2};
        int targetSum = 9;

        System.out.println("Input: " + Arrays.toString(numbers));
        System.out.println("Target: " + targetSum);
        System.out.println("Subset exists (space-optimized): " +
            canAchieveTargetOptimized(numbers, targetSum));

        // Demonstrate the bug: left-to-right iteration gives wrong answer for certain inputs
        System.out.println("\n--- Demonstrating the left-to-right BUG ---");
        int[] bugTestNumbers = {3, 5};
        int bugTarget = 11;  // NOT achievable — no subset of {3,5} sums to 11
        System.out.println("Input: " + Arrays.toString(bugTestNumbers) + ", Target: " + bugTarget);
        System.out.println("Correct answer (right-to-left): " +
            canAchieveTargetOptimized(bugTestNumbers, bugTarget));  // false
        System.out.println("Buggy answer (left-to-right):   " +
            canAchieveTargetBuggy(bugTestNumbers, bugTarget));      // true (wrong! uses 3 multiple times)
    }

    /**
     * CORRECT space-optimized solution.
     * Inner loop runs RIGHT TO LEFT to preserve previous-row semantics.
     */
    public static boolean canAchieveTargetOptimized(int[] numbers, int targetSum) {
        // dp[s] = true means sum s is achievable using elements processed so far
        boolean[] dp = new boolean[targetSum + 1];

        // Base case: sum 0 is always achievable (empty subset)
        dp[0] = true;

        for (int number : numbers) {
            // CRITICAL: iterate RIGHT TO LEFT so we don't reuse the same element
            // Reading dp[sum - number] must reflect the state BEFORE this element was considered
            for (int sum = targetSum; sum >= number; sum--) {
                // If (sum - number) was achievable before, now sum is achievable by including 'number'
                dp[sum] = dp[sum] || dp[sum - number];
            }
        }

        return dp[targetSum];
    }

    /**
     * BUGGY version — left-to-right iteration.
     * This silently solves Unbounded Knapsack instead of Subset Sum.
     * An element can be 'included' multiple times because we read updated values.
     */
    public static boolean canAchieveTargetBuggy(int[] numbers, int targetSum) {
        boolean[] dp = new boolean[targetSum + 1];
        dp[0] = true;

        for (int number : numbers) {
            // BUG: iterating left-to-right means dp[sum - number] may already
            // reflect the inclusion of 'number' earlier in this same pass.
            // Result: 'number' can be used more than once.
            for (int sum = number; sum <= targetSum; sum++) {
                dp[sum] = dp[sum] || dp[sum - number];
            }
        }

        return dp[targetSum];
    }
}

package io.thecodeforge.subsetsum;

import java.util.*;

public class SubsetSumEdgeCases {

    // Correct 1D DP with shift for negative numbers
    public static boolean canAchieveTargetWithNegatives(int[] numbers, int target) {
        int min = Arrays.stream(numbers).min().orElse(0);
        if (min < 0) {
            int shift = -min;
            target += shift * numbers.length; // adjust target – note: this is correct only if we know subset size? Actually simpler: shift each element, target stays? Let's use HashMap approach for clarity.
            // Actually better to shift each element but then the subset sum shifts by shift * k where k is subset size. That's not safe.
            // So we'll use HashMap approach:
            return canAchieveTargetHashMap(numbers, target);
        }
        // else standard DP
        return canAchieveTargetOptimized(numbers, target);
    }

    // HashMap-based DP handles negatives correctly
    public static boolean canAchieveTargetHashMap(int[] numbers, int target) {
        Set<Integer> reachable = new HashSet<>();
        reachable.add(0);
        for (int num : numbers) {
            // We must use a temporary set to avoid reuse in the same pass
            Set<Integer> next = new HashSet<>(reachable);
            for (int sum : reachable) {
                next.add(sum + num);
            }
            reachable = next;
        }
        return reachable.contains(target);
    }

    // Bitset optimization for large W
    public static boolean canAchieveTargetBitset(int[] numbers, int target) {
        BitSet bits = new BitSet(target + 1);
        bits.set(0);
        for (int num : numbers) {
            // Shift bitset left by num and OR with original (right-to-left equivalent)
            BitSet shifted = bits.get(num, target + 1); // but this is left-aligned
            // Actually bitset easier: iterate backwards manually
            // For simplicity, we just show the concept.
            // Real implementation: for (int s = target; s >= num; s--) if (bits.get(s - num)) bits.set(s);
            // But BitSet doesn't support that directly. Instead we can use an array of longs.
            // See java.util.BitSet for actual usage.
        }
        // placeholder
        return false;
    }

    // Reuse optimized DP from previous section (assume it's the same)
    public static boolean canAchieveTargetOptimized(int[] numbers, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int number : numbers) {
            for (int sum = target; sum >= number; sum--) {
                dp[sum] = dp[sum] || dp[sum - number];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        // Test with zeros
        int[] withZero = {0, 5, 7};
        System.out.println("With zero, target 5: " + canAchieveTargetOptimized(withZero, 5)); // true
        System.out.println("With zero, target 0: " + canAchieveTargetOptimized(withZero, 0)); // true

        // Test with negatives
        int[] withNegatives = {-3, 5, 2};
        System.out.println("With negatives, target 4: " + canAchieveTargetHashMap(withNegatives, 4)); // true (5 + -3 + 2? Actually 5+(-3)+2=4, yes)
        System.out.println("With negatives, target -1: " + canAchieveTargetHashMap(withNegatives, -1)); // true (5 + -3 + -3? no, can't reuse, but -3 alone? yes -3, but base is 0, can get -3, then 2? 0+(-3) = -3, then -3+2=-1, etc.)
    }
}

package io.thecodeforge.subsetsum;

import java.util.*;

public class SubsetSumReconstruct {

    public static void main(String[] args) {
        int[] numbers = {3, 34, 4, 12, 5, 2};
        int target = 9;

        List<Integer> subset = getSubset(numbers, target);
        System.out.println("Subset: " + subset); // [5, 4] or [3, 4, 2]
    }

    /**
     * Returns a list of elements that sum to target, or empty list if impossible.
     * This uses parent-pointer reconstruction which works with any DP variant.
     */
    public static List<Integer> getSubset(int[] numbers, int target) {
        int n = numbers.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        // Fill DP table and record choices
        for (int i = 1; i <= n; i++) {
            int elem = numbers[i - 1];
            for (int s = 1; s <= target; s++) {
                dp[i][s] = dp[i - 1][s];
                if (s >= elem && dp[i - 1][s - elem]) {
                    dp[i][s] = true;
                }
            }
        }

        if (!dp[n][target]) return Collections.emptyList();

        List<Integer> subset = new ArrayList<>();
        int remaining = target;
        for (int i = n; i > 0 && remaining > 0; i--) {
            // If the sum could be achieved without element i, it must have been skipped
            if (dp[i - 1][remaining]) continue;
            // Otherwise it must have been included
            subset.add(numbers[i - 1]);
            remaining -= numbers[i - 1];
        }
        return subset;
    }

    /**
     * Space-optimized version with parent pointer.
     * parent[s] stores the index of the last element that made sum s reachable (or -1 if reachable via empty set).
     */
    public static List<Integer> getSubsetOptimized(int[] numbers, int target) {
        boolean[] dp = new boolean[target + 1];
        int[] parent = new int[target + 1];
        Arrays.fill(parent, -1);
        dp[0] = true;
        parent[0] = -2; // marker for empty set

        for (int i = 0; i < numbers.length; i++) {
            int elem = numbers[i];
            for (int s = target; s >= elem; s--) {
                if (!dp[s] && dp[s - elem]) {
                    dp[s] = true;
                    parent[s] = i; // record which element led to this sum
                }
            }
        }

        if (!dp[target]) return Collections.emptyList();

        List<Integer> subset = new ArrayList<>();
        int s = target;
        while (s > 0) {
            int idx = parent[s];
            if (idx == -1) break; // safety
            subset.add(numbers[idx]);
            s -= numbers[idx];
        }
        return subset;
    }
}