2. Subset Sum Problem

public class SubsetSumProblem { static boolean dp[][];

public static boolean isSubsetExists(int[] nums, int n, int sum) {
    dp = new boolean[n + 1][sum + 1];

    // Base Case: If sum is 0, subset always exists (empty subset)
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    // Base Case: If there are no elements and sum > 0, subset cannot be formed
    for (int j = 1; j <= sum; j++) {
        dp[0][j] = false;
    }

    // DP Table Filling
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (nums[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][sum];
}

public static void main(String[] args) {
    int n = 6;
    int sum = 9;
    int[] arr = {3, 34, 4, 12, 5, 2};

    System.out.println("Subset with sum " + sum + " exists: " + isSubsetExists(arr, n, sum));
}

}

### **Approach:**
1. **Define DP State:**  
   - `dp[i][j]` → `true` if a subset of the first `i` elements can form sum `j`.

2. **Base Case:**  
   - If sum = `0`, an empty subset always satisfies → `dp[i][0] = true`.  
   - If `i=0` but `sum > 0`, subset is not possible → `dp[0][j] = false`.  

3. **Transition Formula:**  
   - If `nums[i-1] ≤ j`:  
     ```java
     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
     ```
   - Otherwise, exclude the element:  
     ```java
     dp[i][j] = dp[i - 1][j];
     ```

4. **Final Answer:**  
   - `dp[n][sum]` tells if it's possible to form `sum` using `n` elements.

### **Complexity:**
- **Time Complexity:** `O(n × sum)`
- **Space Complexity:** `O(n × sum)`

### **Example Output:**

Subset with sum 9 exists: true

✅ **Efficient DP-based approach**  
✅ **Solves the subset sum problem optimally**  
✅ **Copy-paste ready format**