C program to create a subsets using backtracking method.

The subset sum problem asks: given a set of integers and a target sum, find all subsets of the set whose elements add up to the target. It is a classic application of backtracking — a systematic method that builds candidates incrementally and abandons a partial candidate (“prunes”) as soon as it determines the candidate cannot lead to a valid solution.

The original post used conio.h, void main(), and declared the variable n twice (once as a global and once as a local — the local shadowed the global). This rewrite uses global scope only for shared state, eliminates Turbo C headers, and adds proper pruning with a remaining-sum parameter to avoid redundant recursion.

How Backtracking Works for Subset Sum

At each position idx, we make a binary choice: include w[idx] in the current subset, or exclude it. We then recurse to position idx + 1 for each choice. Two pruning conditions stop early exploration:

1. If the current sum already equals the target, print the subset and return — no need to add more elements.
2. If the current sum plus all remaining elements still cannot reach the target (even including everything), abandon this branch.

Sorting the input first improves pruning effectiveness because large elements are encountered later, making the second condition trigger earlier on infeasible branches.

C Program: Find All Subsets Summing to a Target (Backtracking)

/* Find all subsets that sum to a target value (backtracking)
 * Compile: gcc -ansi -Wall -Wextra subsets.c -o subsets */
#include <stdio.h>

#define MAX 50

static int w[MAX];    /* set elements (sorted ascending) */
static int inc[MAX];  /* inc[i]=1 means w[i] is included in current subset */
static int target;    /* target sum */
static int n;         /* number of elements */
static int found;     /* count of subsets found */

static void print_subset(void)
{
    int i;
    printf("  { ");
    for (i = 0; i < n; i++)
        if (inc[i]) printf("%d ", w[i]);
    printf("}\n");
    found++;
}

/* idx: current index, cur: running sum, rem: sum of elements from idx onward */
static void backtrack(int idx, int cur, int rem)
{
    if (cur == target) {
        print_subset();
        return;
    }
    if (idx == n) return;
    /* Pruning: even adding all remaining elements cannot reach target */
    if (cur + rem < target) return;

    /* Branch 1: include w[idx] */
    if (cur + w[idx] <= target) {
        inc[idx] = 1;
        backtrack(idx + 1, cur + w[idx], rem - w[idx]);
        inc[idx] = 0;
    }

    /* Branch 2: exclude w[idx] */
    backtrack(idx + 1, cur, rem - w[idx]);
}

/* Simple insertion sort (ascending) */
static void sort_asc(void)
{
    int i, j, tmp;
    for (i = 1; i < n; i++) {
        tmp = w[i];
        for (j = i; j > 0 && w[j-1] > tmp; j--)
            w[j] = w[j-1];
        w[j] = tmp;
    }
}

int main(void)
{
    int i, total = 0;

    printf("Enter number of elements (max %d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX) {
        printf("Invalid input.\n");
        return 1;
    }

    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        if (scanf("%d", &w[i]) != 1) { printf("Invalid.\n"); return 1; }
        total += w[i];
    }

    printf("Enter target sum: ");
    if (scanf("%d", &target) != 1 || target < 0) {
        printf("Invalid target.\n");
        return 1;
    }

    sort_asc();
    found = 0;

    printf("\nSubsets of { ");
    for (i = 0; i < n; i++) printf("%d ", w[i]);
    printf("} that sum to %d:\n", target);

    backtrack(0, 0, total);

    if (found == 0)
        printf("  (none)\n");
    printf("\nTotal subsets found: %d\n", found);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra subsets.c -o subsets
./subsets

Sample Runs

Set {1, 2, 3, 4, 5}, target = 5:

Enter number of elements (max 50): 5
Enter 5 elements:
1 2 3 4 5
Enter target sum: 5

Subsets of { 1 2 3 4 5 } that sum to 5:
  { 1 4 }
  { 2 3 }
  { 5 }

Total subsets found: 3

Set {3, 1, 2, 4}, target = 6 (note: input is unsorted, program sorts it):

Enter number of elements (max 50): 4
Enter 4 elements:
3 1 2 4
Enter target sum: 6

Subsets of { 1 2 3 4 } that sum to 6:
  { 1 2 3 }
  { 2 4 }

Total subsets found: 2

Set {1, 2, 3}, target = 10 (no solution):

Subsets of { 1 2 3 } that sum to 10:
  (none)

Total subsets found: 0

Backtracking Trace — Set {1, 2, 3, 4, 5}, Target = 5

Code Explanation

• static globals — w[], inc[], target, n, and found are declared with static at file scope. This means they are zero-initialized at program start (no need to initialize inc[] manually) and are not visible outside this translation unit.
• Three-parameter backtrack(idx, cur, rem) — passing rem (the sum of all elements from idx onward) avoids recomputing it at each node. The key pruning: if cur + rem < target, there is no way to reach the target even including everything remaining, so return immediately.
• Include branch guard: cur + w[idx] <= target — only attempt to include w[idx] if doing so does not already exceed the target. This prunes the include branch without diving into a recursive call that would immediately return.
• inc[] restored to 0 after include branch — after the include branch returns, inc[idx] = 0 is set before the exclude branch. This is the “undo” step of backtracking — the state is restored so the exclude branch sees a clean slate.
• Insertion sort for ascending order — sorting the input ensures we encounter smaller elements first. This makes the pruning condition (cur + rem < target) fire earlier because once we exceed the target, adding the remaining (larger) elements is even more likely to overshoot.

What This Program Teaches

• Backtracking template: choose → explore → unchoose — the three steps in backtrack()’s include branch are: set inc[idx] = 1 (choose), recurse (explore), set inc[idx] = 0 (unchoose). This template applies to all backtracking problems: N-Queens, Sudoku, graph coloring, and permutation generation.
• Pruning reduces exponential blowup — without pruning, subset sum explores 2^n paths. The two pruning conditions cut off large portions of the search tree early. For sets where most elements are larger than the target, pruning makes backtracking efficient in practice even though the worst case remains O(2^n).
• Global state for recursive helpers — in C, passing many values through each level of recursion adds overhead and noise. Shared global state (the set, the target, the include flags) is a practical pattern for backtracking helpers that only print results rather than returning values. In larger programs, group these into a struct and pass a pointer.
• Subset sum vs. power set — this program finds subsets that sum to a specific target. To generate all 2^n subsets (the power set), remove the target check and always print; or use the include/exclude structure without the pruning condition. Both use the same choose–explore–unchoose structure.

Related Programs

• 0-1 Knapsack in C (Dynamic Programming)
• Binary Search in C
• Shell Sort in C
• Recursion in C — Complete Guide
• Binomial Coefficients in C

Recommended book:
The C Programming Language — Kernighan & Ritchie (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.