> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/subset-sum-problem.md).

# Subset Sum Problem

Given a set of non-negative integers, and a value *sum*, determine if there is a subset of the given set with sum equal to given *sum*.\
**Example:**

```
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True  
There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
```

```java
public class Solution {
    public static boolean sumToK(int[] arr, int n, int K) {
        boolean dp[][] = new boolean[n + 1][K + 1];
        // Base case -> if K=0 then ans=True
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= K; k++) {
                if (arr[i - 1] <= k)
                    dp[i][k] = (dp[i - 1][k] || dp[i - 1][k - arr[i - 1]]);
                else
                    dp[i][k] = dp[i - 1][k];
            }
        }
        return dp[n][K];
    }
}
```