Subset Sum Problem: Interactive Dynamic Programming Visualization

Description

The Subset Sum problem is a classic algorithmic challenge where we need to determine if there exists a subset of given numbers that adds up to a specific target sum. This problem is a special case of the Knapsack problem and is NP-complete.

History

The Subset Sum problem has its roots in theoretical computer science and optimization theory. It was first formally studied in the context of NP-completeness theory in the 1970s. Richard Karp included it in his landmark 1972 paper "Reducibility Among Combinatorial Problems", where he proved that 21 different problems, including Subset Sum, were NP-complete. This discovery helped establish the foundation for computational complexity theory and our understanding of algorithmic efficiency.

Visualization

Numbers:

Target Sum:

Speed:

Enter numbers and target sum, then click Start

Implementation


def subset_sum(numbers, target):
    def backtrack(index, current_sum):
        # Base cases
        if current_sum == target:
            return True
        if index >= len(numbers) or current_sum > target:
            return False
            
        # Include current number
        if backtrack(index + 1, current_sum + numbers[index]):
            return True
            
        # Exclude current number
        return backtrack(index + 1, current_sum)
    
    return backtrack(0, 0)

# Example usage
if __name__ == "__main__":
    numbers = [3, 7, 4, 2, 6]
    target = 13
    
    result = subset_sum(numbers, target)
    print(f"Subset with sum {target} {'exists' if result else 'does not exist'}")


class SubsetSum {
private:
    bool backtrack(vector<int>& nums, int target, int index, int currentSum) {
        // Base cases
        if (currentSum == target) return true;
        if (index >= nums.size() || currentSum > target) return false;
        
        // Include current number
        if (backtrack(nums, target, index + 1, currentSum + nums[index]))
            return true;
            
        // Exclude current number
        return backtrack(nums, target, index + 1, currentSum);
    }
    
public:
    bool hasSubsetSum(vector<int>& nums, int target) {
        return backtrack(nums, target, 0, 0);
    }
};

int main() {
    vector<int> numbers = {3, 7, 4, 2, 6};
    int target = 13;
    
    SubsetSum solution;
    bool result = solution.hasSubsetSum(numbers, target);
    
    cout << "Subset with sum " << target 
         << (result ? " exists" : " does not exist") << endl;
    
    return 0;
}


public class SubsetSum {
    private bool Backtrack(int[] nums, int target, int index, int currentSum) {
        // Base cases
        if (currentSum == target) return true;
        if (index >= nums.Length || currentSum > target) return false;
        
        // Include current number
        if (Backtrack(nums, target, index + 1, currentSum + nums[index]))
            return true;
            
        // Exclude current number
        return Backtrack(nums, target, index + 1, currentSum);
    }
    
    public bool HasSubsetSum(int[] nums, int target) {
        return Backtrack(nums, target, 0, 0);
    }
}

public class Program {
    public static void Main() {
        int[] numbers = {3, 7, 4, 2, 6};
        int target = 13;
        
        var solution = new SubsetSum();
        bool result = solution.HasSubsetSum(numbers, target);
        
        Console.WriteLine($"Subset with sum {target} {(result ? "exists" : "does not exist")}");
    }
}

Complexity Analysis

Time Complexity

The time complexity of this backtracking solution is O(2^n), where n is the number of elements:

For each element, we have two choices: include or exclude
This creates a binary tree of possibilities with height n
Total number of possible combinations is 2^n

Space Complexity

The space complexity is O(n), which includes:

Recursion stack space: O(n)
- Maximum depth of recursion tree is n
- Each recursive call stores constant extra space

Quick Info

Subset Sum Problem