O(sum)空间中的子集和问题


难度级别 中等
经常问 土砖 亚马逊 德瑞斯蒂软件
排列 动态编程

问题陈述

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

使用案列

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

O(sum)空间中的子集和问题

O(sum)空间中子集和问题的方法

任何人都可以想到的最简单的方法是创建所有子集并取它们的总和。 现在检查该总和是否等于给定的输入总和,对吗? 该方法是正确的。 毫无疑问。 但是有一个问题,我们不能有效地创建所有子集。 子集的创建本身具有O(2 ^ N)的时间复杂度。 因此,我们必须考虑其他解决问题的有效方法。

好的,让我们以这种方式考虑这个问题。 我们知道有些子集有一些总和。 现在,对于当前元素,我们有两个选择,要么将其添加到已经存在的子集中,要么不将其添加到子集中。 因此,现在我们知道我们需要做什么。 概括起来,我们将对总和(即从1到输入总和的值)进行循环。 由于这有点令人困惑。 我们将输入的总和称为“目标”,并且必须遍历该总和。 我们将用“ i”代表它们。 对于每个i,我们检查是否不采用当前元素,“我们是否有一个总和等于i的子集?”。 或者,如果采用当前元素,可以使总和等于i吗? 因此,我们可以改写最后一条声明。 如果我们从i中减去当前元素的值,是否有一个子集的总和等于i-current元素的总和?

因此,现在我们只需要确定是否可以形成一个总和等于i或等于i-current元素的子集即可。

现在如何解决呢? 我们将使用 动态编程 解决这个问题。 如果可以使用从2到i的元素获得总和等于j的子集,则将创建一个二维数组或[i,j]单元为真的矩阵。 否则,它是错误的。

递归公式

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

从递归公式中,我们知道当前行仅依赖于最后一行。 因此我们可以避免仅保留两行而不是n个元素的n行。 一行将充当最后一个元素的行,另一行充当当前元素的行。 这是众所周知的DP优化。

代码

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(总和) 因为我们没有为每个元素使用行。 取而代之的是,我们仅使用了两行来存储当前元素和最后一个元素的中间结果。 因此,空间复杂度是线性的。