# O（sum）空间中的子集和问题

## 问题陈述

“ O（sum）空间中的子集总和”问题指出，您得到了一些非负整数和特定值的数组。 现在找出是否有一个子集的总和等于给定输入值的总和。

## 使用案列

```Array = {1, 2, 3, 4}
targetSum = 7```
`The subset having sum equal to given input is possible`

## O（sum）空间中子集和问题的方法

### 递归公式

`dp[i][j] = dp[i-1][j] | dp[i-1][j-input[i]]`

## 代码

### O（sum）空间中子集总和问题的C ++代码

```#include<bits/stdc++.h>
using namespace std;

#include <stdio.h>
#include <stdbool.h>

bool findSubset(int arr[], int n, int targetSum)
{
// dp array to store if any sum is possible
bool dp[2][targetSum + 1];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= targetSum; j++) {

// subset with sum equal to zero is always possible
// we don't choose any element
if (j == 0)
dp[i % 2][j] = true;
// j != 0 and i ==0
else if (i == 0)
dp[i % 2][j] = false;
// current element is greater than the current value of sum(j)
// so take OR of two conditions
// 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
// 2. We don't take the current element
else if (arr[i - 1] <= j)
dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
// Here we cannot take the current element
// So simply check is such a subset is possible
else
dp[i % 2][j] = dp[(i + 1) % 2][j];
}
}

return dp[n % 2][targetSum];
}

int main(){
// Number of elements
int n;cin>>n;
// array to store non-negative numbers
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int targetSum;
cin>>targetSum;
bool can = findSubset(a, n, targetSum);
if(can == true)
cout<<"The subset having sum equal to given input is possible";
else
cout<<"None of the subsets have sum equal to given input";
}
```
```4
1 2 3 4
6```
`The subset having sum equal to given input is possible`

### O（sum）空间中子集和问题的Java代码

```import java.util.*;

class Main{

static boolean findSubset(int arr[], int n, int targetSum)
{
// dp array to store if any sum is possible
boolean dp[][] = new boolean[2][targetSum + 1];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= targetSum; j++) {

// subset with sum equal to zero is always possibe
// we don't choose any element
if (j == 0)
dp[i % 2][j] = true;
// j != 0 and i ==0
else if (i == 0)
dp[i % 2][j] = false;
// current element is greater than the current value of sum(j)
// so take OR of two conditions
// 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
// 2. We don't take the current element
else if (arr[i - 1] <= j)
dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
// Here we cannot take the current element
// So simply check is such a subset is possible
else
dp[i % 2][j] = dp[(i + 1) % 2][j];
}
}

return dp[n % 2][targetSum];
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);

// Number of elements
int n = sc.nextInt();
// array to store non-negative numbers
int a[] = new int[n];
for(int i=0;i<n;i++)
a[i] = sc.nextInt();
int targetSum = sc.nextInt();
boolean can = findSubset(a, n, targetSum);
if(can == true)
System.out.println("The subset having sum equal to given input is possible");
else
System.out.println("None of the subsets have sum equal to given input");
}
}```
```4
1 2 3 4
6```
`The subset having sum equal to given input is possible`

## 复杂度分析

### 时间复杂度

O（Sum * N）， 因为我们遍历了所有元素并检查了从0到给定输入和的每个和值，是否可以？ 因此，时间复杂度是多项式。

### 空间复杂度

O（总和） 因为我们没有为每个元素使用行。 取而代之的是，我们仅使用了两行来存储当前元素和最后一个元素的中间结果。 因此，空间复杂度是线性的。