Combination Sum
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/
* Problem: Combination Sum
* Group: 07. Recursion
*/
/
* ============================================================================================
* PROBLEM: Combination Sum
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given an array of candidate numbers A and a target number B, find all unique combinations
* in A where the candidate numbers sum to B.
*
* Key Rules:
* 1. Unlimited Usage: The same number from A may be chosen an unlimited number of times.
* 2. Non-Descending Order: Elements within a combination must be sorted (e.g., [2, 2, 3]).
* 3. Lexicographical Output: The list of combinations must be sorted.
* 4. Unique Sets: The solution set must not contain duplicate combinations.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Let F(index, currentSum, path) be a recursive function that attempts to build a valid combination.
*
* Pre-processing (Critical Step):
* The input array A may contain duplicates (e.g., [2, 2, 3]). Since we can use any element
* unlimited times, having multiple copies of '2' is redundant and will cause duplicate combinations.
* Step 1: Sort A.
* Step 2: Remove duplicates from A.
*
* Decision Tree (Backtracking):
* At any specific step with currentSum and starting at index:
* 1. Iterate through distinct elements A[i] starting from index to size-1.
* (We start from index and not index + 1 because we can reuse the same element).
* 2. If (currentSum + A[i] > B):
* Stop exploring this path (since A is sorted, all subsequent elements will also be too large).
* 3. If (currentSum + A[i] == B):
* We found a valid combination. Add {path + A[i]} to results.
* 4. If (currentSum + A[i] < B):
* Add A[i] to path.
* Recurse: F(i, currentSum + A[i], path) -> Note we pass 'i', allowing reuse.
* Backtrack: Remove A[i] from path.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= |A| <= 20 (Input size is small)
* 1 <= B <= 500 (Target sum)
*
* Time Complexity:
* O(N^(T/M)) where N is number of candidates, T is target, M is minimum value in A.
* This is an exponential search, but the constraints allow it.
*
* Space Complexity:
* O(T/M) - The maximum depth of the recursion stack (longest possible combination).
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input:
* - Integer array A.
* - Integer B (Target).
*
* Output:
* - A list of lists (Vector of Vectors) containing all valid combinations.
*
* ---------------------
* 5. Examples
* ---------------------
* Input 1: A = [2, 3], B = 2
* - Try 2: Sum=2 (Match). Add [2].
* - Try 3: Sum=3 (>2). Stop.
* Output 1: [[2]]
*
* Input 2: A = [2, 3, 6, 7], B = 7
* Path [2]:
* -> [2, 2]:
* -> [2, 2, 2]: Sum 6. Next try 2 (Sum 8 > 7). Try 3 (Sum 9 > 7). Backtrack.
* -> [2, 2, 3]: Sum 7 (Match). Add [2, 2, 3].
* Path [3]:
* -> [3, 3]: Sum 6. Next try... (No match).
* Path [7]: Sum 7 (Match). Add [7].
* Output 2: [[2, 2, 3], [7]]
*
* ============================================================================================
*/
public class CombinationSum {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> input1, int i) {
return new ArrayList<>();
}
}