Python Program To Check Combo Sum

Count the number of combinations (1 or more integers) from a list that add up to a given target sum S

Understand the Problem

Problem Statement

Given N integers, count how many different combinations of these integers (using 1 or more elements) sum to a target value S.

A combination is considered different if it uses a different set of elements from the original array (order doesn't matter, but elements can be repeated if they appear multiple times in input).

Constraints

1 ≤ N ≤ 25
-10⁵ ≤ S ≤ 10⁵
Array elements can be negative, zero, or positive
Combinations must use 1 or more integers from the input
Each element can be used at most once per combination

Examples

Example 1

Input

4
10 20 50 20
50

Output

Explanation

The two combinations that sum to 50 are: [50] and [10, 20, 20]. Note that we have two 20s in the input, so [10, 20, 20] is valid.

Example 2

Input

7
3 9 -10 7 -12 -2 -5
0

Output

Explanation

The five combinations that sum to 0 are: [3, 9, -12], [7, -2, -5], [3, 7, -10], [3, 9, 7, -12, -2, -5], [3, 9, -10, -2].

Example 3

Input

3
1 2 3
4

Output

Explanation

Only one combination sums to 4: [1, 3]. The combination [2, 2] is not valid since we only have one '2' in the input.

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int target;
    scanf("%d", &target);
    
    int count = 0;
    
    // Generate all non-empty subsets using bit manipulation
    // There are 2^n possible subsets, we skip the empty subset (0)
    for (int mask = 1; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                sum += arr[i];
            }
        }
        if (sum == target) {
            count++;
        }
    }
    
    printf("%d\n", count);
    return 0;
}

Time:O(2^N * N)

Space:O(1)

Approach:

Algorithm: Uses bit manipulation to generate all possible non-empty subsets.

Each bit in an integer represents whether an element is included in the subset
Loop through all masks from 1 to 2^n - 1 (excluding empty subset)
For each mask, sum the elements corresponding to set bits
Count subsets where sum equals target

Key points:

Time complexity: O(2^N * N) - we check 2^N subsets, each taking O(N) to sum
Space complexity: O(1) - only using input array and a few variables
Bit operations (mask & (1 << i)) efficiently check if element i is in subset

Visual Explanation

Loading diagram...

All Problems