Subset-Sum-using-Backtracking

An efficient backtracking approach to solve the subset sum problem, supporting both positive and negative integers.

🔍 Subset Sum using Backtracking

This project implements a Backtracking algorithm to find all subsets of a given list of integers (including both positive and negative numbers) whose sum equals a specified target value.

---

Features

• Works with both positive and negative integers
• Finds all possible subsets that match the target sum
• Uses recursive backtracking
• Simple and easy-to-understand implementation

---

Problem Statement

Given a list of integers (size up to 30), find all subsets whose sum is exactly equal to a target value provided by the user.

---

Approach

• Use backtracking to explore all possible subsets

• At each step:

  • Include the current element
  • Recurse to the next element
  • Backtrack (remove element)

• If the subset sum equals the target → store the subset

---

Code

def find_subsets(nums, target):
    result = []

    def backtrack(start, current_subset, current_sum):
        if current_sum == target:
            result.append(current_subset[:])
            return
        
        for i in range(start, len(nums)):
            current_subset.append(nums[i])
            backtrack(i + 1, current_subset, current_sum + nums[i])
            current_subset.pop()

    backtrack(0, [], 0)
    return result

nums = list(map(int, input().split()))
target = int(input())

subsets = find_subsets(nums, target)

for s in subsets:
    print(s)

---

How to Run

1. Clone the repository
2. Run the Python file:

python subset_sum.py

3. Enter input:

   • First line: integers separated by space
   • Second line: target sum

---

Example

Input

1 -1 2 3 -2
3

Output

[1, 2]
[3]
[1, -1, 3]
[2, 3, -2]

---

Complexity

• Time Complexity: O(2^n)
• Space Complexity: O(n)

---

Notes

• Suitable for small datasets (n ≤ 30)
• May take longer time for large inputs due to exponential complexity

---

Future Improvements

• Optimize using Meet-in-the-Middle
• Add Dynamic Programming approach
• Improve performance with pruning techniques

---