Readmd

# 🔍 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

```python
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:

```bash
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

---