Backtracking VTU BCSL40A

Subset Sum Problem

Q: What is backtracking?

Backtracking is a systematic way of trying out different sequences of decisions until you find one that works. When a dead end is reached, it undoes (backtracks) the last decision and tries another.

Q: How does pruning improve efficiency in Subset Sum?

If current sum + set[k] > d, we skip including set[k] and any further elements (since the set is sorted). This prunes large portions of the search tree.

The Subset Sum problem uses backtracking to find all subsets of a given set whose elements sum to a target value.

Time Complexity

O(2ⁿ)

Space Complexity

O(n)

Paradigm

Backtracking

Introduction

The Subset Sum Problem is a classic backtracking problem: given a set of positive integers and a target sum, find all subsets whose elements add up to the target. It is a fundamental NP-complete problem with applications in cryptography, resource allocation, and partition problems.

Problem Statement

Given a set S = {s1, s2, ..., sn} of positive integers (in increasing order) and a target sum d, find all subsets T ⊆ S such that the sum of elements in T equals d.

Real World Applications

→ Cryptography and public-key schemes based on subset sum
→ Budget partitioning and financial planning
→ Load balancing in parallel computing
→ Game level design and puzzle generation
→ Circuit partition problems

Algorithm Explanation

The backtracking approach explores a state space tree. At each level k, we either include set[k] in the current subset (x[k]=1) or exclude it (x[k]=0). We prune branches where: the current sum already exceeds d (can't reach target), or the remaining elements can't reach d. When the current sum equals d, we print the subset.

Step-by-Step Procedure

1 Sort the input set in increasing order.
2 Check feasibility: total sum < d or smallest element > d → no solution.
3 Call sumofsub(s=0, k=1) where s is current sum, k is current index.
4 Include set[k]: if s + set[k] == d, print subset.
5 If s + set[k] < d and k+1 ≤ n, recurse with set[k] included.
6 Exclude set[k]: if possible to still reach d, recurse with set[k] excluded.
7 Backtrack and try remaining possibilities.

Complete C Program

set.c

View on GitHub ↗

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

int set[10], x[10], n, d;

void sumofsub(int s, int k) {
    int i, f = 1;
    x[k] = 1;
    if(s + set[k] == d) {
        printf("{ ");
        for(i = 1; i <= n; i++) {
            if(x[i] == 1) {
                if(!f) printf(", ");
                printf("%d", set[i]);
                f = 0;
            }
        }
        printf(" }\n");
    } else {
        if(s + set[k] < d && k + 1 <= n) {
            sumofsub(s + set[k], k + 1);
            x[k + 1] = 0;
        }
        if(s + set[k + 1] <= d && k + 1 <= n) {
            x[k] = 0;
            sumofsub(s, k + 1);
            x[k + 1] = 0;
        }
    }
}

int main() {
    int i, sum = 0;
    printf("Enter the Number of Elements: ");
    scanf("%d", &n);
    printf("Enter Elements in Increasing Order: ");
    for(i = 1; i <= n; i++) scanf("%d", &set[i]);
    printf("Enter the Target Sum: ");
    scanf("%d", &d);
    for(i = 1; i <= n; i++) sum += set[i];
    printf("Subsets summing to %d:\n", d);
    if(sum < d || set[1] > d)
        printf("No subsets possible!\n");
    else
        sumofsub(0, 1);
    return 0;
}

Sample Input & Output

Sample Input

5
1 2 3 4 5
6

Expected Output

Subsets summing to 6:
{ 1, 2, 3 }
{ 1, 5 }
{ 2, 4 }

Dry Run / Trace

Set={1,2,3,4,5}, d=6.
Include 1: recurse with s=1
  Include 2: recurse with s=3
    Include 3: s+3=6=d → print {1,2,3} ✓
    Exclude 3, include 4: s=1+2+4=7>6, skip.
  Exclude 2, include 3: s=1+3=4
    Include 4: s=1+3+4=8>6, skip.
  Exclude 3, include 4: s=1+4=5, include 5: s=10>6.
Exclude 1: include 2: ... → {1,5}, {2,4} found similarly.

Advantages & Disadvantages

✓ Advantages

+ Finds all possible subsets summing to target
+ Pruning reduces search space significantly
+ Low space complexity O(n) using recursion stack
+ Easy to understand and implement

✗ Disadvantages

− Worst case O(2ⁿ) — exponential time
− Not practical for large sets
− Elements must be in sorted order for proper pruning

Viva Questions & Answers

Q1. What is backtracking?

Backtracking is a systematic way of trying out different sequences of decisions until you find one that works. When a dead end is reached, it undoes (backtracks) the last decision and tries another.

Q2. How does pruning improve efficiency in Subset Sum?

If current sum + set[k] > d, we skip including set[k] and any further elements (since the set is sorted). This prunes large portions of the search tree.

Q3. What is the state space tree for Subset Sum?

A binary tree where each level corresponds to an element. The left branch includes the element (x[k]=1) and the right branch excludes it (x[k]=0).

Q4. Is Subset Sum NP-Complete?

Yes, the decision version of Subset Sum (does any subset sum to d?) is NP-Complete. The optimization version is NP-Hard.

Q5. How is Subset Sum different from 0/1 Knapsack?

Subset Sum asks to find subsets that exactly sum to d. 0/1 Knapsack maximizes profit subject to a weight constraint. Subset Sum has no objective function — it's a feasibility problem.