Subset Sum Problem in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdbool.h>

bool isSubsetSum(int arr[], int n, int sum) {
    if (sum == 0) return true;
    if (n == 0 && sum != 0) return false;

    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);

    return isSubsetSum(arr, n - 1, sum) || 
           isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}

int main() {
    int arr[] = {3, 34, 4, 12, 5, 2};
    int sum = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isSubsetSum(arr, n, sum))
        printf("Found a subset with the given sum\n");
    else
        printf("No subset with the given sum\n");
    return 0;
}

C Output

Found a subset with the given sum

C++ Program

#include <iostream>
using namespace std;

bool isSubsetSum(int arr[], int n, int sum) {
    if (sum == 0) return true;
    if (n == 0 && sum != 0) return false;

    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);

    return isSubsetSum(arr, n - 1, sum) ||
           isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}

int main() {
    int arr[] = {3, 34, 4, 12, 5, 2};
    int sum = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isSubsetSum(arr, n, sum))
        cout << "Found a subset with the given sum\n";
    else
        cout << "No subset with the given sum\n";
    return 0;
}

C++ Output

Found a subset with the given sum

JAVA Program

public class Main {
    static boolean isSubsetSum(int[] arr, int n, int sum) {
        if (sum == 0) return true;
        if (n == 0 && sum != 0) return false;

        if (arr[n - 1] > sum)
            return isSubsetSum(arr, n - 1, sum);

        return isSubsetSum(arr, n - 1, sum) || 
               isSubsetSum(arr, n - 1, sum - arr[n - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int sum = 9;
        int n = arr.length;
        if (isSubsetSum(arr, n, sum))
            System.out.println("Found a subset with the given sum");
        else
            System.out.println("No subset with the given sum");
    }
}

JAVA Output

Found a subset with the given sum

Python Program

def is_subset_sum(arr, n, sum_val):
    if sum_val == 0:
        return True
    if n == 0 and sum_val != 0:
        return False

    if arr[n - 1] > sum_val:
        return is_subset_sum(arr, n - 1, sum_val)

    return is_subset_sum(arr, n - 1, sum_val) or \
           is_subset_sum(arr, n - 1, sum_val - arr[n - 1])

arr = [3, 34, 4, 12, 5, 2]
sum_val = 9
n = len(arr)
if is_subset_sum(arr, n, sum_val):
    print("Found a subset with the given sum")
else:
    print("No subset with the given sum")

Python Output

Found a subset with the given sum

Explanation

Example

You have the numbers {3, 34, 4, 12, 5, 2} and you want to check if any subset sums to 9. Recursion divides this into smaller problems: either the last number is included in the subset or it is not. If we take 2, then we now seek 7 in the rest of the numbers. If we do not take 2, we still seek 9 in the rest of the numbers. This is repeated until either the total equals 0 (success) or there are no numbers remaining (failure). 

Real-Life Analogy

Imagine packing for a trip with a strict weight restriction. You consider each item individually, deciding if it should go in the luggage or not. Your aim is to hit the given weight precisely. Recursion here is like an assistant that tries out all combinations until it finds a perfect match or realizes that it's not possible.

Why It Matters

Subset sum problem is a building block for numerous algorithmic problems such as knapsack problem, partition problem, and even cryptography usage. It familiarizes you with how to approach problems where you have to choose between adding or subtracting elements in order to achieve something.

Learning Insights

This example shows decision tree recursion where each step branches into two possibilities. It’s an excellent way to understand exponential complexity and why certain problems are hard to solve quickly. It also teaches the importance of base cases: if sum == 0, we’ve succeeded; if we’ve run out of numbers without reaching 0, we’ve failed.

Use in Interviews and Projects

For interviews, the subset sum problem is a popular choice since it checks recursion comprehension, reasoning, and awareness of complexity. For actual projects, this can come in handy in resource allocation, algorithms for financial planning, or matching systems where exact satisfaction of constraints is necessary.

SEO-Friendly Closing

The subset sum problem in C, C++, Java, and Python illustrates how to tackle difficult decision problems with step-by-step inclusion or exclusion of components. This is a fundamental technique in combinatorial search, optimization techniques, and constraint satisfaction problems, and thus is crucial for coding interviews and real-world applications in scheduling, finance, and data analysis.