A focused collection of subset, subarray, and subsequence problems implemented in C++ using recursion and backtracking. Each problem demonstrates different approaches to generating and filtering combinations from arrays.
| # | Problem | Approach | Data Structure |
|---|---|---|---|
| 1 | Subset Return (2D Dynamic Array) | Recursion | int** (heap-allocated) |
| 2 | Subset Return (2D Vector) | Recursion | vector<vector<int>> |
| 3 | Subset Print (1D Array) | Backtracking | int[] with sentinel -1 |
| 4 | Subset Sum = K (Return) | Constrained Recursion | int[][] (static) |
| 5 | Subset Sum = K (Print) | Constrained Backtracking | int[] with sentinel -1 |
Input:
3
1 2 3
Output:
3
2
2 3
1
1 3
1 2
1 2 3
Input:
4
2 1 3 2
K = 4
Output:
2 2
1 3
- Recursive subset generation — include/exclude each element to explore 2^n combinations
- Backtracking — build solutions incrementally and prune invalid paths
- Dynamic vs static allocation — compare
new int*[]vsvector<vector<int>> - Constrained search — filter subsets by a target sum
| Metric | Value |
|---|---|
| Time (generate all subsets) | O(n * 2^n) |
| Space (store all subsets) | O(n * 2^n) |
| Time (print subsets) | O(2^n) |
g++ -o subsets subsets.cpp
./subsetsrecursion backtracking subsets subarrays subsequences dynamic-programming cpp competitive-programming algorithms data-structures